Sachverhalt:
A. A.a R._, geboren 1967, ist seit dem Jahre 2003 im Gastgewerbe tätig. Am 29. Juni 2004 meldete sie sich unter Hinweis auf chronische Hepatitis C (bestehend seit einigen Jahren) und Herzrhythmusstörungen (bestehend "seit ca. 4-5 Monaten") bei der Invalidenversicherung zum Rentenbezug an. Die IV-Stelle des Kantons Wallis führte medizinische und erwerbliche Abklärungen durch. Am 18. Juli 2007 verfügte sie die Zusprechung einer ganzen Rente ab 1. Mai 2005 sowie einer halben Rente ab 1. Mai 2007. Eine hiegegen erhobene Beschwerde der R._ wies das Versicherungsgericht des Kantons Wallis mit Entscheid vom 14. Februar 2008 ab.
A.b Im Rahmen eines Revisionsverfahrens holte die IV-Stelle erneut medizinische Beurteilungen ein und verfügte nach durchgeführtem Vorbescheidverfahren am 25. Mai 2010 die Aufhebung der Rente (bei einem Invaliditätsgrad von 29 %).
B. Hiegegen erhob R._ Beschwerde. Nachdem sowohl R._ als auch die IV-Stelle weitere ärztliche Beurteilungen ins Recht gelegt hatten, wies das Versicherungsgericht des Kantons Wallis die Beschwerde mit Entscheid vom 17. Mai 2011 ab.
C. R._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und unter Aufhebung des angefochtenen Entscheides die Rückweisung der Sache zur weiteren Abklärung und neuen Verfügung an die Vorinstanz respektive an die Beschwerdegegnerin beantragen. Sodann sei der vorinstanzliche Kostenentscheid aufzuheben und die Höhe des Anwaltshonorars auf Fr. 3'785.40 festzulegen. In verfahrensrechtlicher Hinsicht ersucht sie um Gewährung der unentgeltlichen Rechtspflege. Eventualiter sei die IV-Stelle zu verpflichten, ihr rückwirkend ab 1. August 2010 weiterhin eine halbe Rente auszurichten.
Im Nachgang zur Beschwerde lässt sie eine Stellungnahme des Dr. med. S._ vom 14. Mai 2011 zu den Akten reichen.
Die IV-Stelle schliesst auf Abweisung der Beschwerde, das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (Art. 105 Abs. 1 und 2 BGG).
2. Das kantonale Gericht hat die Rechtsgrundlagen zur Rentenrevision (<ref-law> in Verbindung mit Art. 88a und 88bis IVV; <ref-ruling> E. 5 S. 110 ff.) korrekt wiedergegeben. Darauf kann verwiesen werden. Zutreffend ist namentlich, dass neue medizinische Feststellungen revisionsrechtlich nur bedeutsam sind, wenn sie eine tatsächliche Veränderung der (gesundheitlichen) Verhältnisse zum Ausdruck bringen. Hingegen stellt die bloss andere, abweichende Beurteilung eines im Wesentlichen gleich gebliebenen Sachverhalts keine revisionsbegründende oder im Rahmen der Revision relevante Änderung dar (z.B. Urteil 8C_219/2009 vom 25. August 2009 E. 2.2 mit Hinweisen).
3. 3.1 Die Vorinstanz stellte fest, der psychische Gesundheitszustand der Versicherten habe sich verbessert und erwog, die Überprüfung des Rentenanspruches durch die Beschwerdegegnerin sei somit zu Recht erfolgt. Es könne davon ausgegangen werden, dass die Versicherte bei Aufbietung allen guten Willens in Nachachtung der Schadenminderungspflicht eine angepasste Tätigkeit zu 70 % ausüben könnte. Unter Berücksichtigung des von der IV-Stelle zugestandenen leidensbedingten Abzuges von 10 % resultiere ein rentenausschliessender IV-Grad von 29 %.
3.2 Die Beschwerdeführerin rügt zur Hauptsache, das kantonale Gericht habe den Untersuchungsgrundsatz verletzt und den Sachverhalt unrichtig festgestellt. Eine revisionsrechtlich relevante Tatsachenänderung sei nicht ausgewiesen.
4. Aus somatischer Sicht sind unbestritten keine wesentlichen Veränderungen eingetreten. Am 29. Oktober 2009 bemerkte die RAD-Ärztin H._, FMH Innere Medizin, Folgendes: "Im Status zeigen sich keine wesentlichen Veränderungen im Vergleich zu 2007. Neu bestehen Parästhesien palmarseits der Finger 1, 2 und 3 links bei aber normaler Greiffunktion und Kraft der oberen Extremität. Die Verspannung des M. Trapezius links kann durch Therapie verbessert werden; diese neuen Ausfälle bewirken keine zusätzliche Arbeitsunfähigkeit bei den bereits formulierten Limitationen. Somit kann die bereits 2007 vorgesehene Steigerung im Verlauf auf eine 70 % AF in adaptierter Tätigkeit statuiert werden." Am 25. November 2009 präzisierte die RAD-Ärztin, die Gesamtsituation habe sich seit 2007 stabilisiert, aus psychiatrischer Sicht werde seit längerem keine antidepressive Therapie mehr wahrgenommen, die soziale Problematik habe sich beruhigt, was auch die psychische Situation stabilisiere. Aus somatischer Sicht sei keine Verschlechterung eingetreten, die Versicherte arbeite zu 50 % in einer - mit Blick auf die Nachtschichten und die langen Arbeitstage mit Arbeitszeiten von bis zu 9 3⁄4 Stunden am Stück - dem Gesundheitszustand "nicht wirklich angepassten Tätigkeit". Es bestehe insofern eine Verbesserung, dass keine psychiatrische Medikation mehr nötig sei und potenzielle somatische Ursachen hätten ausgeschlossen werden können. Somit sei eine "relative Verbesserung" eingetreten. An der bereits 2007 vorgeschlagenen Steigerung der Arbeitsfähigkeit auf 70 % könne festgehalten werden. Es erscheine schlüssig und nachvollziehbar, dass bei 50 %iger Arbeitsfähigkeit in einer nicht adaptierten Tätigkeit eine den Limitationen angepasste Arbeit zu 70 % zumutbar sei.
5. 5.1 Entscheidend ist, ob die Vorinstanz die von der RAD-Ärztin mit Blick auf eine Verringerung der "sozialen Problematik" festgestellte psychische Stabilisierung zu Recht als revisionsbegründende Tatsachenänderung qualifizierte (E. 2 hievor).
5.2 Eine erhebliche Verbesserung des psychischen Gesundheitszustandes ist beispielsweise anzunehmen, wenn eine ursprünglich festgestellte depressive Episode nach fachärztlicher Feststellung abgeklungen ist (Urteil 9C_617/2009 vom 15. Januar 2010 E. 3.2.1). So verhält es sich hier nicht. Abgesehen davon, dass selbst die RAD-Ärztin ausdrücklich festhielt, der Gesundheitszustand habe sich "seit 2007 nicht wesentlich verändert" (vgl. vorangehende E. 4), spielten die depressiven Episoden nach - von den behandelnden Ärzten abweichenden - Einschätzung des RAD bereits im Jahre 2007 keine entscheidende Rolle (mehr). So hielt RAD-Psychiater C._, Arzt für Psychiatrie und Psychotherapie, am 6. Februar 2007 fest, die antidepressive Therapie scheine zu greifen, im Gegensatz zu Oktober 2006 liege keine mittelgradige Depression mehr vor. Er diagnostizierte - lediglich - eine Neurasthenie (F48.0) und stellte differenzialdiagnostisch eine Panikstörung sowie einen Zustand nach depressiven mittelgradigen Episoden (F32.1) fest. Dr. med. H._ führte gleichentags aus, durch "eine Verbesserung der Müdigkeit nach Abklärung und allfälliger Therapieeinleitung durch die Hausärztin wäre eine progressive Verbesserung der Arbeitsfähigkeit bei entsprechendem supportiven Coaching auf 70 % durchaus zu erwarten".
5.3 Dass sich die rasche Ermüdbarkeit der Versicherten gebessert hätte oder anderweitige erhebliche (psychische) Verbesserungen eingetreten wären, geht aus den Akten aber nicht hervor. Nicht nur spricht Dr. med. H._ von einer im Wesentlichen unveränderten Gesundheitssituation und es ist auch der Beurteilung des RAD-Arztes B._, Arzt für Psychiatrie und Psychotherapie (Bericht vom 5. November 2009), zu entnehmen, dass aus psychiatrischer Sicht "weiterhin die seit der letzten Untersuchung im RAD im Frühjahr festgestellte AUF von 30 % gegeben" sei. Sondern auch die behandelnden Ärzte Dr. med. S._, FMH Allgemeine Medizin, (Bericht vom 22. April 2009), med. pract. R._, Oberärztin am Psychiatriezentrum (welche allerdings eine Steigerung der Arbeitsfähigkeit auf 60 % zu einem späteren Zeitpunkt unter der Voraussetzung einer weiteren Stabilisierung für möglich erachtete; Bericht vom 24. Juni 2009) und Dr. med. V._, Spezialarzt für Innere Medizin (Bericht vom 14. September 2009), gingen von einer im Wesentlichen unveränderten Situation bei einer Arbeitsfähigkeit von - weiterhin - 50 % aus. Damit aber ist die Beurteilung der RAD-Ärztin H._, wonach (in einer angepassten Tätigkeit) die Arbeitsfähigkeit nunmehr auf 70 % gesteigert werden könne, lediglich eine andere medizinische Einschätzung eines im Wesentlichen gleich gebliebenen Gesundheitszustandes. Eine anspruchserhebliche Verbesserung des psychischen Gesundheitszustandes erscheint nicht überwiegend wahrscheinlich und es ist auch nicht davon auszugehen, dass weitere (Akten-) Beurteilungen zur Entwicklung des Gesundheitszustandes zwischen dem 18. Juli 2007 (ursprüngliche Verfügung) und dem 25. Mai 2010 (Rentenaufhebungsverfügung) zu wesentlich anderen Erkenntnissen zu führen vermöchten, weshalb darauf zu verzichten ist (antizipierte Beweiswürdigung). Die vorinstanzliche Schlussfolgerung, wonach eine wesentliche tatsächlichen Änderung zu bejahen sei, hält vor Bundesrecht nicht stand. Nach dem Grundsatz der materiellen Beweislast bleibt es demzufolge beim bisherigen Rechtszustand (Urteil 9C_418/2010 vom 29. August 2011 E. 3.1 mit Hinweis).
6. Soweit mit der Beschwerde die Höhe des anwaltlichen Honorars im Rahmen der unentgeltlichen Verbeiständung im vorinstanzlichen Verfahren gerügt wird, ist sie von vornherein unzulässig, da eine von einem kantonalen Gericht festgesetzte Entschädigung im Rahmen der unentgeltlichen Verbeiständung nur vom Rechtsvertreter beim Bundesgericht angefochten werden kann (vgl. Urteil 8C_802/2010 vom 3. November 2010 E. 4 mit Hinweis auf <ref-ruling> E. 2 S. 363 f. e contrario; ARV 1996/97 Nr. 27 S. 151), während die beschwerdeführende Person selber dazu nicht legitimiert ist, ebenso wenig der Rechtsvertreter, wenn er, wie hier, im Namen seiner Mandantin Beschwerde führt (SVR 2007 UV Nr. 16 S. 54 E. 2.1, U 63/04; Urteil 9C_163/2009 vom 10. September 2010 E. 6). Auf das entsprechende Rechtsbegehren ist daher nicht einzutreten. Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind indes die Kosten- und Entschädigungsfolgen im kantonalen Verfahren neu zu regeln.
7. Entsprechend dem Ausgang des Verfahrens sind die Gerichtskosten der unterliegenden Beschwerdegegnerin aufzuerlegen (<ref-law>). Diese hat der obsiegenden Beschwerdeführerin eine Parteientschädigung auszurichten (<ref-law>). Das Gesuch um unentgeltliche Prozessführung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Der Entscheid des Kantonalen Versicherungsgerichts des Wallis vom 17. Mai 2011 und die Verfügung der Kantonalen IV-Stelle Wallis vom 25. Mai 2010 werden aufgehoben.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an des kantonale Versicherungsgericht des Wallis zurückgewiesen.
4. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
5. Dieses Urteil wird den Parteien, dem Kantonalen Versicherungsgericht des Wallis und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 6. Januar 2012
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Bollinger Hammerle