Sachverhalt: A. A.a Die 1986 geborene A._ war seit Juli 2002 in der Drogerie S._ angestellt und damit bei der Winterthur Schweizerische Versicherungs-Gesellschaft (nunmehr AXA Versicherungen AG) gegen Unfälle versichert. Am 21. April 2004 stürzte sie auf einer Treppe aufs Knie, nachdem sich ihr rechtes Knie ausgerenkt hatte. Dr. med. H._ führte daraufhin am 11. Mai 2004 im Spital X._ eine Kniearthroskopie durch und nahm eine Teilmeniskektomie des medialen Meniskushinterhorns, ein Shaving der vorderen Kreuzbandreste und eine Gelenktoilette vor. Nach zunächst befriedigendem Verlauf traten im August 2004 ein Kniegelenkserguss und antero-mediale Schmerzen auf. Im Bericht vom 24. November 2004 attestierte Dr. med. H._ eine vollständige Beschwerdefreiheit und Heilung der Unfallverletzung. Die AXA Versicherungen AG kam bis Ende November 2004 für die Heilbehandlung auf und richtete für die Zeit vom 24. April bis 30. Juni 2004 Taggelder aus. A.b Am 6. Oktober 2006 meldete A._ der AXA Versicherungen AG einen Rückfall zum Unfallereignis vom 21. April 2004. Zuvor hatte sie während der Sanitätsrekrutenschule im Sommer 2006 eine erste und während der Kaderschule im Herbst 2006 auf der Hindernisbahn eine zweite giving-way-Symptomatik erlitten, was die unfreiwillige frühzeitige Entlassung aus dem Militärdienst zur Folge hatte. Dr. med. H._ diagnostizierte am 12. Oktober 2006 rezidivierende giving-way-Symptomatiken rechts bei vorderer Kreuzbandinsuffizienz und bejahte die Indikation für eine Stabilisierungsoperation. Am 31. Oktober 2006 nahm er im Spital X._ eine Kreuzbandersatzplastik vor. Mit Verfügung vom 27. Juni 2007 verneinte der Unfallversicherer den natürlichen Kausalzusammenhang zwischen dem Unfallereignis vom 21. April 2004 und den nach dem 30. November 2004 bestehenden Beschwerden. Daran hielt er mit Einspracheentscheid vom 21. November 2007 fest. B. Die dagegen erhobene Beschwerde wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 18. Mai 2009 ab. C. A._ lässt Beschwerde erheben mit den Rechtsbegehren, es sei festzustellen, dass ein Rückfall zum Unfall vom 21. April 2004 vorliegt, und es sei die AXA Versicherungen AG zu verpflichten, die gesetzlichen Versicherungsleistungen auszurichten. Eventuell sei die Sache zur Durchführung ergänzender Abklärungen an den Unfallversicherer zurückzuweisen. Überdies wird um Durchführung eines zweiten Schriftenwechsels ersucht. Sowohl die AXA Versicherungen AG wie auch das Bundesamt für Gesundheit und das kantonale Gericht verzichten auf eine Vernehmlassung. 