Sachverhalt:
A. A._, geboren 1962, arbeitete seit Dezember 2004 als Küchenhilfe im Restaurant X._ und war in dieser Eigenschaft bei der Berner Allgemeine Versicherungs-Gesellschaft (später: Allianz Suisse Versicherungs-Gesellschaft; nachfolgend: Allianz oder Beschwerdeführerin) obligatorisch gegen Unfälle und Berufskrankheiten versichert. Bei einem Misstritt mit anschliessendem Sturz auf einer schlecht beleuchteten Treppe am Arbeitsplatz zog sich die Versicherte am 12. Februar 2005 eine Distorsion des oberen Sprunggelenks (OSG) rechts zu. Während Dr. med. S._ am 14. Februar 2005 röntgenologisch eine Fraktur ausschliessen konnte, zeigte die Magnetresonanz-Untersuchung vom 4. April 2005 ein deutliches Knochenmarksödem. Bereits mit der Physiotherapieverordnung des Dr. med. T._ vom 19. April 2005 wurde zusätzlich zur OSG-Distorsion rechts ein Morbus Sudeck diagnostiziert. Auch Dr. med. Z._ vom kantonalen Spital Y._ wies auf einen Morbus Sudeck nach Supinationstrauma des OSG rechts hin (Bericht vom 22. April 2005). Nach verzögertem Heilungsverlauf und umfangreichen spezialmedizinischen Abklärungen stellte die Allianz die erbrachten gesetzlichen Versicherungsleistungen (Heilbehandlung und Taggeld) gestützt auf das Gutachten vom 2. März 2007 ihres Vertrauensarztes Dr. med. H._, Facharzt FMH für Chirurgie, speziell Allgemein- und Unfallchirurgie, des Spitals W._ (nachfolgend: vertrauensärztliches Gutachten) per 28. Februar 2007 ein und sprach der Versicherten für die ihr unfallbedingt verbleibende Integritätseinbusse von 10% eine entsprechende Integritätsentschädigung zu (Verfügung vom 4. Juni 2007). Daran hielt die Allianz nach Kenntnisnahme von dem durch die Invalidenversicherung veranlassten polydisziplinären Gutachten der Medizinischen Abklärungsstation des Spitals B._ vom 17. Dezember 2007 (nachfolgend: MEDAS-Gutachten) mit Einspracheentscheid vom 10. April 2008 fest.
B. Die hiegegen erhobene Beschwerde, mit welcher A._ im Wesentlichen unter Aufhebung des Einspracheentscheides vom 10. April 2008 die weitere Ausrichtung der gesetzlichen Versicherungsleistungen ab 1. März 2007 beantragte, hiess das Versicherungsgericht des Kantons St. Gallen gut (Entscheid vom 5. März 2009).
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten stellt die Allianz das Rechtsbegehren, der angefochtene kantonale Gerichtsentscheid sei aufzuheben und der Einspracheentscheid vom 10. April 2008 zu bestätigen.
Während A._ auf Abweisung der Beschwerde schliesst sowie um Gewährung der unentgeltlichen Rechtspflege und unentgeltlichen Verbeiständung ersucht, verzichtet das Bundesamt für Gesundheit (BAG) auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 1.4.1 S. 254).
Im Beschwerdeverfahren um die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung ist das Bundesgericht nicht an die vorinstanzliche Feststellung des rechtserheblichen Sachverhalts gebunden (Art. 97 Abs. 2 und Art. 105 Abs. 3 BGG).
2. Die Allianz hat im Einspracheentscheid vom 10. April 2008, auf welchen der angefochtene Gerichtsentscheid verweist, die Bestimmungen über den Anspruch auf Leistungen der Unfallversicherung im Allgemeinen (<ref-law> [in Verbindung mit <ref-law>]) sowie auf Heilbehandlung (<ref-law>) und Taggeld im Besonderen (<ref-law>) zutreffend wiedergegeben. Gleiches gilt für die dargelegten Grundsätze über den für einen Leistungsanspruch nebst anderem vorausgesetzten natürlichen Kausalzusammenhang zwischen dem Unfall und dem eingetretenen Schaden (Krankheit, Invalidität, Tod; <ref-ruling> E. 3.1 S. 181 mit Hinweisen). Korrekt sind auch die Ausführungen zur Rechtsprechung über den im Weiteren erforderlichen adäquaten Kausalzusammenhang (<ref-ruling> E. 3.2 S. 181 mit Hinweis). Richtig sind sodann die Hinweise zum Wegfall des ursächlichen Zusammenhangs und damit des Leistungsanspruchs der versicherten Person bei Erreichen des Status quo sine vel ante (SVR 2009 UV Nr. 3 S. 9, 8C_354/2007 E. 2.2), zu dem im Sozialversicherungsrecht bei der Beantwortung von Tatfragen üblichen Beweisgrad der überwiegenden Wahrscheinlichkeit (<ref-ruling> E. 3.1 S. 181 mit Hinweisen) sowie zum Beweiswert und zur Beweiswürdigung medizinischer Berichte und Gutachten (<ref-ruling> E. 1c S. 160 mit Hinweisen; vgl. auch <ref-ruling> E. 3 S. 352 mit Hinweisen). Darauf wird verwiesen.
3. Vorweg ist festzuhalten, dass die Beschwerdeführerin mit Verfügung vom 4. Juli 2007, bestätigt durch Einspracheentscheid vom 10. April 2008, der Versicherten eine Integritätsentschädigung auf Grund einer Integritätseinbusse von 10% zugesprochen hat, welche gemäss vertrauensärztlichem Gutachten auf einer der Beschwerdegegnerin dauerhaft verbleibenden unfallbedingten Beweglichkeitseinschränkung am oberen und unteren Sprunggelenk des rechten Fusses basiert. Ohne diese Schätzung des Integritätsschadens in Frage zu stellen, hat die Allianz dem Gutachten ihres Vertrauensarztes volle Beweiskraft zuerkannt und basierend auf dieser Beurteilung auch die Heilbehandlung und das Taggeld per 28. Februar 2007 eingestellt.
4. 4.1 Die Vorinstanz gelangte nach umfassender Würdigung der gesamten Aktenlagen zur Auffassung, auch das MEDAS-Gutachten und insbesondere die Beurteilung des neurologischen Fachgutachters der MEDAS Dr. med. N._ liessen auf ein CRPS (complex regional pain syndrome) schliessen. Diese Einschätzung steht laut angefochtenem Entscheid in Übereinstimmung mit den übrigen medizinischen Akten, in welchen praktisch lückenlos ein Morbus Sudeck diskutiert worden sei. Eine Beeinträchtigung des Heilungsverlaufes durch den Morbus Sudeck könne jedenfalls für den Zeitpunkt der Leistungseinstellung (28. Februar 2007) nicht mit dem Beweisgrad der überwiegenden Wahrscheinlichkeit verneint werden, weshalb die Allianz weiterhin verpflichtet sei, der Versicherten für die Folgen des Unfalles vom 12. Februar 2005 die gesetzlichen Leistungen zu erbringen.
4.2 Demgegenüber argumentiert die Beschwerdeführerin, sowohl aus dem vertrauensärztlichen als auch aus dem MEDAS-Gutachten lasse sich übereinstimmend die Schlussfolgerung ziehen, dass (spätestens) am 1. März 2007 keine objektivierbaren Unfallfolgen mehr feststellbar waren und von einer Fortsetzung der Heilbehandlung keine namhafte Besserung des Gesundheitszustandes mehr zu erwarten gewesen sei. Soweit darüber hinaus organisch nicht objektiv ausgewiesene Beschwerden geklagt würden, seien diese nicht adäquat kausal durch den Unfall vom 12. Februar 2005 verursacht worden.
5. 5.1 Das kantonale Gericht hat die Frage, ob ein Morbus Sudeck (auch: Sudeck'sche Dystrophie, Algodystrophie ohne Nervenläsion oder Complex regional pain syndrome Typ I [CRPS I]; vgl.: NIX/VAN HOUDENHOVE, Komplexes regionales Schmerzsyndrom, in: Egle/Hoffmann/Lehmann/Nix [Hrsg.], Handbuch Chronischer Schmerz, 2003, S. 588; MUMENTHALER/MATTLE, Neurologie, 11. Aufl. 2002, S. 850; ALFRED M. DEBRUNNER, Orthopädie/Orthopädische Chirurgie, 4. Aufl. 2002, S. 481 und 695 f.; HEIERLI/MEYER/RADZIWILL, Nosologischer Rahmen und Terminologie, in: Bär/Felder/Kiener [Hrsg.], Algodystrophie, 1998, S. 7; vgl. Urteil 8C_765/2008 vom 20. Februar 2009 E. 5.1) vorliegt, geprüft und gestützt auf die nicht zu beanstandende Beweiswürdigung festgestellt, dass hier ein solcher organischer bzw. körperlicher Gesundheitsschaden (Urteil 8C_955/2008 vom 29. April 2009 E. 6 mit Hinweisen) für den Zeitpunkt der strittigen Leistungseinstellung nicht mit dem erforderlichen Beweisgrad der überwiegenden Wahrscheinlichkeit zu verneinen ist.
5.2 Was die Beschwerdeführerin hiegegen vorbringt, überzeugt nicht. Zunächst steht die Behauptung, die nach dem 28. Februar 2007 geklagten gesundheitlichen Beeinträchtigungen der Versicherten stünden nicht in einem adäquaten Kausalzusammenhang mit dem Unfall vom 12. Februar 2005 in direktem Widerspruch zur Tatsache, dass die Allianz der Beschwerdegegnerin für die bleibende unfallbedingte Einschränkung der Beweglichkeit im oberen und unteren Sprunggelenk rechts eine Integritätsentschädigung auf Grund einer Integritätseinbusse von 10% zugesprochen hat. Damit hat die Beschwerdeführerin ausdrücklich anerkannt und bisher nicht bestritten, dass die Versicherte eine ihr dauerhaft verbleibende Gesundheitsstörung erlitt, welche in einem natürlich und adäquat kausalen Zusammenhang mit dem Unfall vom 12. Februar 2005 steht.
5.3 Litt die Beschwerdegegnerin über den 28. Februar 2007 hinaus an unfallkausalen Beeinträchtigungen ihrer Gesundheit, bleibt zu prüfen, ob diese Beschwerden ab 1. März 2007 weiterhin behandlungsbedürftig waren und eine unfallbedingte Einschränkung der Arbeitsfähigkeit zur Folge hatten.
5.3.1 Soweit Dr. med. H._ im vertrauensärztlichen Gutachten der Allianz ausführte, zwei Jahre nach dem Unfall sei der Status quo sine erreicht worden, steht diese Aussage im Widerspruch zu seiner Schätzung des Integritätsschadens. Zudem sind den Akten keinerlei Hinweise darauf zu entnehmen, dass am rechten Fussgelenk der Versicherten schon vor dem Unfall ein krankhafter bzw. degenerativer Vorzustand (vgl. SVR 2009 UV Nr. 3 S. 9, 8C_354/2007 E. 2.2 mit Hinweisen) vorhanden war, weshalb sich hier die Frage nach dem Erreichen des Status quo (sine vel ante) mangels Ursachenkonkurrenz nicht stellt (vgl. PETER OMLIN, Die Invalidität in der obligatorischen Unfallversicherung, Diss. Freiburg 1995, 2. unveränderte Aufl. 1999, S. 124 f.).
5.3.2 Dr. med. H._ hielt sodann mit Blick auf die Frage nach dem Behandlungsabschluss (vgl. <ref-law>) fest, dass die therapeutischen Möglichkeiten "nahezu" - jedoch offensichtlich nicht vollständig - ausgeschöpft seien. Denn immerhin schlug er vor, dass noch eine stationäre Behandlung in einer Schmerzklinik und eine psychotherapeutische Behandlung in Frage kämen. Es fällt auf, dass die Beschwerdegegnerin trotz des verzögerten Heilungsverlaufs bis zum strittigen Fallabschluss per 28. Februar 2007 - soweit ersichtlich - nie für eine befristete Zeitdauer stationär in einer Rehabilitationsklinik weilte. Im Übrigen ist die vertrauensärztliche Einschätzung mit der Auffassung der MEDAS-Gutachter zu vereinbaren, wonach "eine Rehabilitation eingeleitet werden" müsse und mit intensiver Physiotherapie sowie manueller Lymphdrainage eine Verbesserung der Arbeitsfähigkeit erreicht werden könne. Auch angesichts der klar feststellbaren somatischen Gesundheitsstörung einer "ödematösen Schwellung des distalen Unterschenkels rechts mit livider Verfärbung der Haut" (gemäss MEDAS-Gutachten S. 13) bzw. einer leicht rötlichen, lividen Verfärbung des ganzen rechten Fusses und des rechten Unterschenkels mit Druckdolenz im Gegensatz zur linken Seite sowie eines leichten Temperaturunterschiedes zwischen dem rechten und dem linken Fuss (gemäss vertrauensärztlichem Gutachten Ziff. 1.2) war über den Fallabschluss per 28. Februar 2007 hinaus von der Fortsetzung einer zweckmässigen Behandlung der Unfallfolgen (vgl. <ref-law>) weiterhin eine namhafte Besserung des Gesundheitszustandes zu erwarten.
5.3.3 Was die Arbeitsfähigkeit anbetrifft, finden sich in den medizinischen Akten teilweise widersprüchliche Angaben zur Bereitschaft der Beschwerdegegnerin, eine ihr allenfalls verbleibende Restarbeitsfähigkeit zu verwerten. Dr. med. U._ berichtete am 5. Juli 2005 von einer sicherlich bestehenden Aggravationskomponente, stellte jedoch gleichzeitig seine weiteren, unfallbedingt erforderlichen Heilbehandlungsmassnahmen nicht in Frage. Demgegenüber schloss Dr. med. H._ anlässlich seiner ersten eingehenden vertrauensärztlichen Untersuchung der Versicherten vom 6. September 2005 unfallfremde Faktoren aus und bejahte damals eine volle Arbeitsunfähigkeit. Auch Dr. med. E._ vom Hand- und Fusszentrum der Klinik C._ attestierte der Beschwerdegegnerin anlässlich der Konsultation vom 6. Dezember 2005 bei klinisch objektivierbaren Befunden und einer glaubhaft eingeschränkten Belastbarkeit des rechten Fusses weiterhin eine volle Arbeitsunfähigkeit. Nach einer erneuten eingehenden Untersuchung der Versicherten vom 16. Mai 2006 verneinte Dr. med. H._ ausdrücklich, dass "eine Aggravation seitens der Patientin [vorliege]" und anerkannte gleichzeitig die volle unfallbedingte Arbeitsunfähigkeit der Beschwerdegegnerin in der angestammten Tätigkeit bei einer damals auf 20% geschätzten Integritätseinbusse. Mit vertrauensärztlichem Gutachten bestätigte Dr. med. H._, dass die Versicherte in der angestammten und jeder anderen Verweisungstätigkeit voraussichtlich dauerhaft voll arbeitsunfähig bleibe, doch sah er nunmehr die anhaltend geklagten Beschwerden als Somatisierungsstörung und verneinte deren Unfallkausalität, trotz nach wie vor unvermindert objektivierbarer Verfärbungen am rechten Fuss und Unterschenkel und einer unbestritten unfallbedingten Einschränkung der Beweglichkeit im oberen und unteren Sprunggelenk. Schliesslich erkannten auch die MEDAS-Gutachter, dass die Beschwerdegegnerin ihre angestammte Tätigkeit als Küchenhilfe seit dem Unfall dauerhaft nicht mehr ausüben könne, dass ihr jedoch eine sitzende Tätigkeit trotz ihres Gesundheitsschadens mit einem zeitlichen Normalarbeitspensum bei einer um 30% eingeschränkten Leistungsfähigkeit zumutbar sei.
5.3.4 Nach dem Gesagten steht fest, dass die Versicherte über den per 28. Februar 2007 verfügten Fallabschluss hinaus an objektiv ausgewiesenen behandlungsbedürftigen Gesundheitsstörungen leidet, welche die Arbeitsfähigkeit einschränken und in einem anspruchsbegründenden Kausalzusammenhang mit dem Unfall vom 12. Februar 2005 stehen. Das kantonale Gericht hat daher zu Recht den mit Einspracheentscheid der Allianz vom 10. April 2008 bestätigten Fallabschluss (mit Einstellung sämtlicher Versicherungsleistungen per 28. Februar 2007 und Zusprache einer Integritätsentschädigung) aufgehoben. Was die Beschwerdeführerin im Übrigen hiegegen vorbringt, ist unbegründet.
6. Die unterliegende Allianz hat die Gerichtskosten zu tragen und der Versicherten eine Parteientschädigung auszurichten (Art. 66 Abs. 1, Art. 68 Abs. 2 BGG; <ref-ruling>, 132 V 215 E. 6.1 S. 235). Das Gesuch der Beschwerdegegnerin um Gewährung der unentgeltlichen Rechtspflege ist damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 750.- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 10. September 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Hochuli