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.