Sachverhalt:
A. A.a Mit Verfügung vom 31. Juli 2001 lehnte die Arbeitslosenkasse Ob- und Nidwalden den Anspruch des 1961 geborenen H._ auf Arbeitslosenentschädigung ab 2. Juli 2001 ab, weil er damals (wie bereits in der Eigenschaft als Verwaltungsratspräsident der kurz zuvor in Insolvenz geratenen B._ AG als Gesellschafter mit Kollektivunterschrift zu zweien mit seiner Ehefrau bei der Kollektivgesellschaft C._ eine arbeitgeberähnliche Stellung innegehabt hatte. Das Eidgenössische Versicherungsgericht (heute: Bundesgericht) bestätigte letztinstanzlich diesen Standpunkt mit Urteil C 63/02 vom 20. November 2002.
A.b Vom 1. September 2003 bis zum 31. Juli 2005 bezog der Versicherte Leistungen der Arbeitslosenversicherung. Gestützt auf eine anonyme Anzeige von der E-Mail-Adresse "..." stellte die Kasse nach Überprüfung der Sachlage fest, dass der Versicherte im fraglichen Zeitraum für die am ... 2004 ins Handelsregister des Kantons Luzern eingetragene und am ... 2006 bereits wieder aufgelöste Firma A._ GmbH tätig war. Nach Gewährung des rechtlichen Gehörs verneinte das Regionale Arbeitsvermittlungszentrum Obwalden und Nidwalden (nachfolgend: RAV oder Beschwerdegegnerin) mit Verfügung vom 30. Mai 2008, bestätigt durch Einspracheentscheid vom 21. Juli 2008, die Vermittlungsfähigkeit für die Dauer vom 1. September 2003 bis 31. Juli 2005 und kündigte die entsprechende Rückforderung der zu Unrecht ausbezahlten Taggelder an.
B. Die hiegegen erhobene Beschwerde des H._ wies das Versicherungsgericht des Kantons Nidwalden mit Entscheid vom 15. Dezember 2008 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt H._ beantragen, der angefochtene Gerichts- und der Einspracheentscheid seien aufzuheben. Zudem sei der Bewerde die aufschiebende Wirkung zu erteilen.
Das RAV und das Staatssekretariat für Wirtschaft verzichten auf eine Vernehmlassung.
D. Mit Verfügung vom 2. November 2009 erkannte das Bundesgericht der Beschwerde aufschiebende Wirkung zu.

Erwägungen:
1. 1.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>).
1.2 Gemäss <ref-law> sind Noven im letztinstanzlichen Verfahren grundsätzlich unzulässig. Die Voraussetzungen, unter denen die vom Beschwerdeführer letztinstanzlich neu eingereichte schriftliche Aussage eines ehemaligen Mitarbeiters des RAV vom 15. August 2009 ausnahmsweise zulässig wäre, sind vorliegend nicht erfüllt, so dass dieses Schreiben unbeachtet bleiben muss.
2. 2.1 Das kantonale Gericht hat die Bestimmungen über den Anspruch auf Arbeitslosenentschädigung und die dafür unter anderem vorausgesetzte Vermittlungsfähigkeit (<ref-law> in Verbindung mit <ref-law>) sowie die dazu ergangene Rechtsprechung, insbesondere bezüglich der Vermittlungsbereitschaft als Teilgehalt der Vermittlungsfähigkeit (<ref-ruling> E. 6a S. 58) und der Vermittlungsfähigkeit bei Ausübung einer selbstständigen Erwerbstätigkeit (ARV 1998 Nr. 32 S. 174, C 248/96 E. 4a; vgl. auch ARV 2002 S. 55, C 353/00 E. 2b), zutreffend dargelegt. Darauf wird verwiesen.
2.2 Im angefochtenen Entscheid richtig wiedergegeben ist auch die Rechtsprechung, wonach der Begriff der Vermittlungs(un)fähigkeit graduelle Abstufungen ausschliesst (<ref-ruling> E. 6a S. 58 mit Hinweisen) und die Vermittlungsfähigkeit zu verneinen ist, wenn der Versicherte nicht bereit oder in der Lage ist, eine Arbeitnehmertätigkeit auszuüben, weil er eine selbstständige Erwerbstätigkeit aufgenommen hat oder aufzunehmen gedenkt, sofern er dadurch nicht mehr als Arbeitnehmer vermittelt werden bzw. seine Arbeitskraft in dieser Eigenschaft nicht so einsetzen kann oder will, wie es ein Arbeitgeber normalerweise verlangt (<ref-ruling> E. 1a mit Hinweisen). Denn ein Versicherter, welcher sich ausschliesslich der Gründung und dem Aufbau einer eigenen Firma widmet, kann nicht als vermittlungsfähig im Sinne von <ref-law> betrachtet werden, da er auf Grund seiner Tätigkeit nicht bereit und in der Lage ist, eine anderweitige Arbeit aufzunehmen (ARV 1990 Nr. 3 S. 25, C 89/89).
3. Soweit die Vorinstanz mit angefochtenem Entscheid in Bezug auf das Einspracheverfahren eine Verletzung des Anspruchs auf rechtliches Gehör durch die Beschwerdegegnerin verneint hat, ist nicht ersichtlich und wird vom Beschwerdeführer auch nicht dargelegt, inwiefern das kantonale Gericht damit Bundesrecht verletzte.
4. Strittig und zu prüfen ist, ob der Versicherte während der Dauer des Bezuges von Arbeitslosenentschädigung vom 1. September 2003 bis 31. Juli 2005 vermittlungsfähig war.
5. 5.1 Bei der Feststellung der Vermittlungsfähigkeit handelt es sich um eine Tatfrage (Urteile 8C_79/2009 vom 25. September 2009 E. 4.3 und 8C_267/2007 vom 17. September 2007 E. 2.1). Das kantonale Gericht hat nach umfassender Würdigung der Aktenlagen für das Bundesgericht in tatsächlicher Hinsicht grundsätzlich verbindlich festgestellt, dass der Beschwerdeführer während der fraglichen Dauer nicht vermittlungsfähig war, weil ihm der Wille zur Aufnahme einer unselbstständigen Erwerbstätigkeit fehlte und die getätigten Stellenbewerbungen lediglich dem bloss formalen Nachweis einer vermeintlich bestehenden Vermittlungsfähigkeit dienten, um ohne eigenes Risiko während der ersten kritischen Phase des Unternehmensaufbaus der A._ GmbH in den Genuss von Arbeitslosenentschädigung zu kommen.
5.2 Demgegenüber macht der Versicherte geltend, er habe "eigenmächtig und im Einverständnis von M._", dem unterzeichnenden Mitglied der Geschäftsleitung der A._ GmbH, das Arbeitszeugnis vom 31. März 2006 abgeändert. Wahr sei, dass er vom 1. August 2005 bis 31. März 2006 als operativer Geschäftsführer der A._ GmbH tätig gewesen sei, nicht jedoch bereits ab 1. September 2003. Auch in seinem Lebenslauf habe der Beschwerdeführer nur zum Zwecke der Verbesserung seines wirtschaftlichen Fortkommens tatsachenwidrig "vorgegeben, dass er [bei der A._ GmbH] seit dem 1. September 2003 angestellt gewesen sei. [...] Um einen Widerspruch zwischen dem Lebenslauf und dem Arbeitszeugnis zu verhindern, [habe er sich] gezwungen [gesehen], auch das Arbeitszeugnis anzupassen." In willkürlicher Beweiswürdigung habe die Vorinstanz aus der beschränkten Beratertätigkeit des Versicherten für die A._ GmbH auf die fehlende Vermittlungsfähigkeit geschlossen. Er sei nur "in geringem Umfang der zu gründenden A._ GmbH zur Seite gestanden". Eine selbstständige Tätigkeit sei auf Grund einer unfallbedingten "100%-igen Arbeitsunfähigkeit ab dem 4. Februar 2004 ohnehin nicht möglich" gewesen.
6. 6.1 Das kantonale Gericht hat in zulässiger antizipierter Beweiswürdigung auf weitere Beweismassnahmen verzichtet. Von einer willkürlichen Beweiswürdigung kann keine Rede sein. Billigte M._, der erste Geschäftsführer der A._ GmbH und Alleinunterzeichner des Arbeitszeugnisses vom 31. März 2006, dass der Beschwerdeführer sein Arbeitszeugnis nachträglich "eigenmächtig" nach seinem freien Willen tatsachenwidrig abänderte, ist nicht zu beanstanden, dass die Vorinstanz auf dessen Einvernahme als Zeuge verzichtet hat. Auch die schriftliche Bestätigung des M._ vom 8. April 2008 muss als Gefälligkeit gegenüber dem Versicherten gewertet werden, weil auch mit diesem Schreiben wiederum klar wahrheitswidrige Sachverhaltsangaben bescheinigt wurden. So trifft es - entgegen der Behauptung des M._ - nachweislich nicht zu, dass der Beschwerdeführer vor dem 1. August 2005 "nicht operativ oder sonst wie für die [A._ GmbH] tätig [war] oder sonst wie in den Diensten der [A._ GmbH stand]".
6.2 Der Versicherte schloss nicht nur den Mietvertrag vom 26. Februar 2004 über die nachmaligen Geschäftsräumlichkeiten der damals unmittelbar vor der Gründung stehenden A._ GmbH ab, sondern beteiligte sich unter anderem auch an der Planung des Ausbaus des Mietobjekts, verfasste Schreiben namens der Geschäftsleitung der A._ GmbH sowie einen Bericht über den Managementplan. In bundesrechtskonformer Würdigung der gesamten Umstände und Aktenlage stellte die Vorinstanz fest, dass der Beschwerdeführer während der zu beurteilenden Zeitspanne sowohl objektiv (infolge eines erheblichen Zeitaufwandes während der Planungs- und Aufbauphase der A._ GmbH) als auch subjektiv (angesichts der engen persönlichen Bindung an die A._ GmbH, welche später eine Anstellung bei dieser Gesellschaft und schliesslich die Übernahme der Geschäftsführung mit Mehrheitsbeteiligung an der A._ GmbH zur Folge hatte) vermittlungsunfähig war.
6.3 Was der Versicherte letztinstanzlich gegen die Sachverhaltsfeststellung des kantonalen Gerichts vorbringt, ist unbegründet. Insbesondere vermag er nicht dazulegen, inwiefern der angefochtene Entscheid willkürlich und damit offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.1 S. 17 f. und 131 I 467 E. 3.1 S. 473 f. je mit Hinweisen). Die Argumentation des Beschwerdeführers ist widersprüchlich. Im März 2006 übernahm er die Mehrheitsbeteiligung an der A._ GmbH und war fortan als einziger Gesellschafter mit Einzelunterschrift zeichnungsberechtigt. Auf Grund der spätestens ab diesem Zeitpunkt anzunehmenden arbeitgeberähnlichen Stellung in der A._ GmbH und der damit verbundenen Missbrauchsgefahr (<ref-ruling> ff.; SVR 2007 AlV Nr. 21 S. 69, C 180/06 E. 3.1 mit Hinweis; Urteil 8C_635/2009 vom 1. Dezember 2009 E. 3.1 mit Hinweisen) ist nicht nachvollziehbar, weshalb sich der Versicherte nach dem Firmenaustritt und dem Erlöschen der Zeichnungsberechtigung des M._ im März 2006 Ende des gleichen Monats ein von M._ unterzeichnetes Arbeitszeugnis ausstellen liess, welches der Beschwerdeführer angeblich später "eigenmächtig" an den von ihm selber verfassten eigenen Lebenslauf anpassen musste (vgl. hievor E. 5.2). Unzutreffend ist ferner die Behauptung, eine selbstständige Tätigkeit sei ab 4. Februar 2004 infolge einer unfallbedingten vollständigen Arbeitsunfähigkeit ausgeschlossen gewesen. Gemäss Unfallschein UVG der Schweizerischen Unfallversicherungsanstalt (SUVA) war der Versicherte - nach der ärztlich bescheinigten vollständigen Arbeitsunfähigkeit ab dem Unfall vom 4. Februar 2004 - erst ab 16. April 2004 wieder zu 50 % arbeitsfähig. Nach Angaben des Beschwerdeführers erlitt er am 4. Februar 2004 einen derart schweren Skiunfall, dass er sich in der Folge "mehreren Operationen" unterziehen musste. Dennoch war er - bei angeblich medizinisch ausgewiesener voller Arbeitsunfähigkeit - bereits am zweiten Tag nach diesem "schweren Unfall" wieder in der Lage, sich namens der Geschäftsleitung der A._ GmbH um die Fortsetzung der Planung des Ausbaus der Geschäftsliegenschaft zu kümmern, das Schreiben vom 6. Februar 2004 zu verfassen und am 26. Februar 2004 - bei weiterhin attestierter voller Arbeitsunfähigkeit - den Mietvertrag über die nachmaligen Geschäftsräumlichkeiten der A._ GmbH abzuschliessen.
6.4 Im Rahmen der bundesgerichtlichen Kognition ist nicht zu beanstanden, dass die Vorinstanz gestützt auf eine umfassende Würdigung der konkreten Umstände entgegen den Angaben des Versicherten darauf schloss, er habe sich während der fraglichen Bezugsdauer von Arbeitslosenentschädigung in einem die Vermittlungsfähigkeit ausschliessenden Ausmass an der Planung und am Aufbau der A._ GmbH beteiligt. Der angefochtene Entscheid basiert weder auf einer offensichtlich unrichtigen Sachverhaltsfeststellung noch hat das kantonale Gericht sonst wie Bundesrecht verletzt.
7. Das Verfahren ist kostenpflichtig (<ref-law>). Die Gerichtskosten werden dem Beschwerdeführer als unterliegender Partei auferlegt (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Nidwalden, Abteilung Versicherungsgericht, der Arbeitslosenkasse Ob- und Nidwalden und dem Staatssekretariat für Wirtschaft schriftlich mitgeteilt.
Luzern, 24. Februar 2010
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Hochuli