Sachverhalt:
A. Mit rechtskräftigen Verfügungen vom 16. Oktober 2001 sprach die IV-Stelle Basel-Stadt der 1953 geborenen B._ nach diversen Abklärungen vom 1. April 1999 bis 31. Dezember 2000 eine ganze Invalidenrente (Invaliditätsgrad 100 %) und ab 1. Januar 2001 eine unbefristete halbe Rente (Invaliditätsgrad 51 %) zu. Am 31. März 2006 meldete sich die Versicherte erneut bei der Invalidenversicherung und machte eine Verschlechterung des Gesundheitszustandes geltend, woraufhin eine Rentenrevision durchgeführt wurde. Nach zusätzlichen medizinischen und erwerblichen Abklärungen, insbesondere dem Beizug eines Gutachtens des Dr. med. A._, Facharzt FMH für Rheumatologie, Physikalische Medizin und Rehabilitation (vom 3. Oktober 2006) und eines Gutachtens des Dr. med. G._, Facharzt FMH für Psychiatrie (vom 6. November 2006), hob die IV-Stelle die Invalidenrente per Ende des der Verfügung folgenden Monats auf (Verfügung vom 24. Juli 2008).
B. Die dagegen erhobene Beschwerde wies das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 23. März 2009 ab.
C. Die Versicherte lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Rechtsbegehren, in Aufhebung des kantonalen Gerichtsentscheides sei die IV-Stelle zu verurteilen, ihr auch nach dem 1. September 2008 auf der Basis eines Invaliditätsgrades von mindestens 51 % eine halbe Rente zu entrichten. Ferner wird um Gewährung der unentgeltlichen Rechtspflege ersucht.
Während die IV-Stelle auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Mit Blick auf diese Kognitionsregelung ist auf Grund der Vorbringen in der Beschwerde ans Bundesgericht zu prüfen, ob der angefochtene kantonale Gerichtsentscheid in der Anwendung der massgeblichen materiell- und beweisrechtlichen Grundlagen (u.a.) Bundesrecht, Völkerrecht oder kantonale verfassungsmässige Rechte verletzt (Art. 95 lit. a-c BGG), einschliesslich einer allfälligen rechtsfehlerhaften Tatsachenfeststellung (Art. 97 Abs. 1, <ref-law>). Hingegen hat unter der Herrschaft des BGG eine freie Überprüfung des vorinstanzlichen Entscheids in tatsächlicher Hinsicht zu unterbleiben, ausser wenn sich die Beschwerde gegen einen Entscheid über die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung richtet (<ref-law>).
2. Streitig und zu prüfen ist, ob die Beschwerdeführerin auch nach dem 1. September 2008 weiterhin Anspruch auf eine mindestens halbe IV-Rente hat.
2.1 Im angefochtenen Entscheid werden die zur Beurteilung dieser Frage massgebenden invaliditäts- und revisionsrechtlichen Grundlagen, insbesondere über die revisionsweise Erhöhung, Herabsetzung oder Aufhebung laufender Invalidenrenten (<ref-law>, <ref-ruling> E. 3.5 S. 349 ff., ferner <ref-ruling> E. 5 S. 110 ff.), den revisionsrechtlich massgebenden Vergleichszeitraum (<ref-ruling>) sowie die Bestimmung des Invaliditätsgrades mittels Einkommensvergleich (<ref-law>) und die Anforderungen an beweiswertige ärztliche Berichte und Gutachten (<ref-ruling> E. 3a S. 352 mit Hinweis; vgl. auch <ref-ruling> E. 5.1 S. 232) zutreffend dargelegt. Darauf wird verwiesen.
2.2 Bei den vorinstanzlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit der versicherten Person handelt es sich grundsätzlich um Entscheidungen über eine Tatfrage (<ref-ruling> E. 3.2 S. 397 ff.). Analoges gilt auch für die Frage, ob sich eine Arbeits(un)fähigkeit in einem bestimmten Zeitraum in einem revisionsrechtlich relevanten Sinne verändert hat (Urteil I 865/06 vom 12. Oktober 2007 E. 4). Die konkrete Beweiswürdigung stellt eine Tatfrage dar. Dagegen ist die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach <ref-law> Rechtsfrage (<ref-ruling> E. 3.2 und 4 S. 397 ff.; Urteil 9C_270/2008 vom 12. August 2008 E. 2.2).
3. 3.1 Die Vorinstanz gelangte nach zutreffender Würdigung der medizinischen Akten - wie bereits die Verwaltung - zu Recht zum Schluss, dass sich der Gesundheitszustand der Beschwerdeführerin seit der ursprünglichen Rentenverfügung vom 16. Oktober 2001 wesentlich verbessert hat und in einer angepassten körperlichen Tätigkeit nunmehr von einer Arbeitsfähigkeit von 85 % auszugehen ist, weshalb sie nach Durchführung eines Einkommensvergleichs bei einem Invaliditätsgrad von 28 % einen weitergehenden Rentenanspruch verneinte. Sie stützte sich dabei auf das rheumatologische Gutachten des Dr. med. A._ vom 3. Oktober 2006 und das psychiatrische Gutachten des Dr. med. G._ vom 6. November 2006, denen sie vollen Beweiswert zuerkannte. Dies ist nicht zu beanstanden, erfüllen diese Expertisen doch alle rechtsprechungsgemässen Anforderungen an eine beweistaugliche medizinische Entscheidgrundlage (<ref-ruling> E. 3a S. 352 mit Hinweis). Die Gutachter attestierten der Versicherten in gesamtmedizinischer Hinsicht in Anbetracht der somatischen und psychiatrischen Befunde in einer adaptierten Tätigkeit eine Arbeitsfähigkeit von 100 % und in der angestammten Tätigkeit als Küchenmitarbeiterin eine Arbeitsfähigkeit zwischen 75 und 80 %.
3.2 Die Einwendungen der Beschwerdeführerin vermögen an der vorinstanzlichen Betrachtungsweise nichts zu ändern. Sie sind nicht geeignet, die für das Bundesgericht grundsätzlich verbindlichen Tatsachenfeststellungen (E. 1 und 2.1) unter dem Blickwinkel der gesetzlichen Kognition als offensichtlich unrichtig oder sonstwie als bundesrechtswidrig (<ref-law>) erscheinen zu lassen. Insbesondere ist nicht ersichtlich, inwiefern der Psychiater Dr. med. G._ denselben Gesundheitszustand mit den gleichen Diagnosen neu beurteilt haben soll, was einer Revision entgegenstände, wie geltend gemacht wird. Die Dres. med. M._ und S._ gingen in ihrem Gutachten vom 21. Februar 2001, welches für die ursprünglichen Verfügungen vom 16. Oktober 2001 massgebend gewesen war, von einer schweren depressiven Episode mit anhaltender somatoformer Schmerzstörung sowie einer posttraumatischen Belastungsstörung als Diagnosen mit Auswirkung auf die Arbeitsfähigkeit aus und gelangten zu einer Arbeitsunfähigkeit von 50 %. In gesamtmedizinischer Hinsicht attestierten sie im ergänzenden Schreiben vom 22. Mai 2001 nach Rücksprache mit der Klinik S._ ebenfalls eine 50%-ige Arbeitsfähigkeit, was mit der Vorinstanz vor allem aus der psychiatrischen Diagnose resultierte. Demgegenüber stellte der Psychiater Dr. med. G._ im Gutachten vom 6. November 2006 keine Diagnose mit Einfluss auf die Arbeitsfähigkeit, sondern hielt vielmehr unter der Überschrift Diagnosen ohne Auswirkung auf die Arbeitsfähigkeit eine anhaltende somatoforme Schmerzstörung und eine rezidivierende depressive Störung, gegenwärtig remittiert, fest. Er führte aus, die anlässlich der Untersuchung vom 20. Mai 2003 noch festgestellte leichte depressive Störung habe sich weitgehend zurückgebildet, und zum aktuellen Zeitpunkt seien keine Hinweise auf eine depressive Störung mehr vorhanden. Damit ist eine Verbesserung des Gesundheitszustandes erstellt und entgegen der Beschwerdeführerin hinreichend belegt, dass nicht bloss eine abweichende Interpretation und Folgenabschätzung hinsichtlich eines im Wesentlichen unveränderten Zustandes stattgefunden hat. Überdies ist, worauf die Beschwerdegegnerin zu Recht hinweist, auch bei gleich gebliebener Diagnose eine Veränderung der gesundheitlichen Verhältnisse möglich, wenn sich ein Leiden in seiner Intensität und in seinen Auswirkungen auf die Arbeitsfähigkeit verändert hat (vgl. Urteil 9C_261/2009 vom 11. Mai 2009 E. 1.2 mit Hinweisen). Nachdem sich der Gesundheitszustand der Beschwerdeführerin entsprechend der verbindlichen vorinstanzlichen Feststellung zumindest betreffend Ausprägung Depression und entsprechender Arbeitsfähigkeit verbessert hat, steht fest, dass die Beschwerdeführerin, zwar weiterhin an derselben Krankheit (einer anhaltenden somatoformen Schmerzstörung) leidet, wie bereits im Zeitpunkt der früheren Verfügung vom 16. Oktober 2001, diese jedoch heute - gerade wegen fehlender Komorbidität - keine Auswirkungen auf die Arbeitsfähigkeit mehr hat. Mithin hat es beim vorinstanzlichen Entscheid sein Bewenden, nachdem die Invaliditätsbemessung selbst nicht beanstandet wird.
4. Das Verfahren ist kostenpflichtig (Art. 65 Abs. 1 und Abs. 4 lit. a BGG). Dem Ausgang des Verfahrens entsprechend hat die Beschwerdeführerin die Gerichtskosten zu tragen (<ref-law>). Dem Gesuch um unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten und der unentgeltlichen Verbeiständung) kann entsprochen werden, da die Bedürftigkeit ausgewiesen ist, das Rechtsmittel nicht aussichtslos und die Vertretung durch einen Anwalt geboten war (Art. 64 Abs. 1 und 2 BGG; <ref-ruling> E. 4a S. 202 und 371 E. 5b S. 372). Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Der Beschwerdeführerin wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden der Beschwerdeführerin auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Advokat Dr. Claude Schnüriger, Basel, wird als unentgeltlicher Anwalt der Beschwerdeführerin bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2800.- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 29. Oktober 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Weber Peter