Sachverhalt:
A. X._ war in den Jahren 2004 und 2005 bei der zur Groupe Mutuel gehörenden La Caisse Vaudoise, Martigny (im Folgenden: Vaudoise), obligatorisch gegen Krankheit versichert. Am 21. Februar 2005 stellte die Vaudoise X._ die Prämien für den Monat April 2005 (Fr. 225.-; zahlbar bis 31. März 2005) sowie eine Kostenbeteiligung von Fr. 1'044.05 (Rechnungsnummer 049127015) und am 29. März 2005 eine Kostenbeteiligung in Höhe von Fr. 317.60 (zahlbar bis 30. April 2005; Rechnungsnummer 051073901) in Rechnung. Nachdem X._ die Prämienrechnung nicht fristgerecht beglichen hatte, mahnte ihn die Vaudoise am 20. April 2005 kostenpflichtig. Auf entsprechende Anfrage vom 25. April 2005 stellte ihm die Vaudoise am 26. April 2005 eine detaillierte Abrechnung zu, welche einen Saldo zu ihren Gunsten in Höhe von Fr. 1'279.05 auswies. Gleichentags teilte X._ der Vaudoise mit, dass er "die Summe von CHF 1207.05 bis auf die Betreibungs- und Mahnspesen von offenbar CHF 118.00 akzeptiere" und eine Einzahlung in Höhe von Fr. 1'089.- veranlasst habe.
Mit Schreiben vom 28. April 2005 erläuterte die Vaudoise ihre Abrechnung vom 26. April 2005 und führte aus, der Saldo zu ihren Gunsten setze sich aus der Prämie April (Fr. 225.-) und der Selbstbehaltrechnung Nr. 049127015 (Fr. 1'044.05) inklusive Mahnspesen von Fr. 10.- zusammen. Weiter erklärte sie, die Mahn- und Betreibungsspesen in Höhe von Fr. 118.- (gemäss Abrechnung vom 26. April 2005) beinhalteten entsprechende Beträge, welche zwischen 1. Januar 2004 und 30. April 2005 in Rechnung gestellt und zwischenzeitlich bis auf Fr. 10.- beglichen worden seien. Die Betreibung betreffe die Prämie für den Monat Mai 2004 inklusive Mahn- und Betreibungsspesen; dass diese nicht an seinem Wohnsitz eingeleitet worden sei, habe X._ zu verantworten, da er es unterlassen habe, ihr seine Wohnsitzverlegung mitzuteilen. In der Folge verrechnete sie die Einzahlung des X._ mit der ausstehenden Kostenbeteiligungsrechnung Nr. 049127015 (in Höhe von Fr. 1'044.05) und schrieb den Restbetrag der April-Prämie gut.
Am 18. Mai 2005 mahnte die Vaudoise X._ bezüglich der Selbstbehaltsrechnung Nr. 051073901 (Fr. 317.60) kostenpflichtig. Am 21. Juni 2006 schliesslich sandte sie X._ zwei - ebenfalls kostenpflichtige - letzte Mahnungen betreffend die Prämie April 2005 (Restbetrag) und die Selbstbehaltsrechnung Nr. 051073901 und leitete in der Folge eine entsprechende Betreibung ein (Zahlungsbefehl vom 19. April 2006; Rechtsvorschlag vom 24. April 2006). Am 5. Mai 2006 erliess sie eine Verfügung und bestätigte diese mit Einspracheentscheid vom 29. Juni 2006.
B. Die hiegegen erhobene Beschwerde des X._ wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 17. November 2006 ab.
C. X._ führt Verwaltungsgerichtsbeschwerde und beantragt die Aufhebung des angefochtenen Entscheides sowie des Einspracheentscheides und die Feststellung, dass er der Vaudoise nichts schulde.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (BGG) ist am 1. Januar 2007 in Kraft getreten (AS 2006 1205 ff., 1243). Da der angefochtene Entscheid vorher ergangen ist, richtet sich das Verfahren noch nach OG (Art. 132 Abs. 1 BGG; <ref-ruling> E. 1.2 S. 395).
2. Soweit Fragen in Zusammenhang mit Prämienforderungen im Raum stehen, handelt es sich dabei nicht um Leistungsstreitigkeiten, weshalb die Überprüfungsbefugnis des Bundesgerichtes diesbezüglich eingeschränkt und nur überprüfbar ist, ob der angefochtene Entscheid Bundesrecht verletzt oder der Sachverhalt offensichtlich unrichtig oder unvollständig festgestellt worden ist (<ref-ruling> E. 2.1 S. 171). Anderes gilt bezüglich Anteilsrechnungen: die damit zusammen hängenden Fragen prüft das Bundesgericht frei (Urteil des Eidg. Versicherungsgerichtes K 40/05 vom 21. Januar 2006 E. 2, publiziert in: RKUV 2006 Nr. KV 356 S. 41 f.).
3. Gemäss Art. 61 Abs. 1 Satz 1 KVG legt der Versicherer die Prämien für seine Versicherten fest. Entrichten Versicherte fällige Prämien und Kostenbeteiligungen trotz Mahnung nicht, hat der Versicherer das Vollstreckungsverfahren einzuleiten (Art. 90 Abs. 3 KVV in der vom 1. Januar 2003 bis 31. Dezember 2005 gültig gewesenen wie auch in der seit 1. Januar 2006 anwendbaren Fassung; <ref-ruling> E. 5 und 6 S. 148 ff.).
4. 4.1 Die Vorinstanz erwog, die Zusammenstellung der Beschwerdegegnerin vom 26. April 2005 sei klar und unmissverständlich. Die streitige Rechnung Nr. 051073901 (Selbstbehalt von Fr. 317.60) sei darin nicht enthalten, weil deren Zahlungsfrist erst am 30. April 2005 abgelaufen sei. Die Beschwerdegegnerin habe dem Beschwerdeführer nie zugesichert, er schulde ihr einzig den Betrag von Fr. 1'279.05. Dass die Versicherung die ihr vom Beschwerdeführer am 29. April 2005 überwiesenen Fr. 11'089.- zur Begleichung der Anteilsrechnung Nr. 049127015 (in Höhe von Fr. 1'044.05) verwendet und den Überschuss der Prämie für April 2005 gutgeschrieben habe, sei korrekt. Schliesslich sei die Erhebung der Mahn-, Dossier- und Zustellkosten (in Höhe von Fr. 30.-, 35.- und 50.-) nicht zu beanstanden. Zum einen enthielten die Allgemeinen Versicherungsbedingungen (AVB; Ausgabe Januar 2005) der Beschwerdegegnerin in Art. 12 Abs. 2 lit. a eine entsprechende Rechtsgrundlage, zum anderen sei deren Höhe angemessen. Der Beschwerdeführer habe seine Wohnsitzverlegung der Beschwerdegegnerin pflichtwidrig nicht mitgeteilt und es somit zu verantworten, dass ihm der Zahlungsbefehl der ersten Betreibung (vom August 2005) nicht habe zugestellt werden können.
4.2 Demgegenüber bringt der Beschwerdeführer vor, bei der Abrechnung vom 26. April 2005 handle es sich um einen "Gesamtsaldo". Mit der Überweisung vom 29. April 2005 habe er in guten Treuen davon ausgehen dürfen, dass er - mit Ausnahme der nicht geschuldeten Mahn- und Betreibungsspesen - sämtliche Ausstände beglichen habe, insbesondere auch die Prämienforderung für April 2005 und die Kostenbeteiligung in Höhe von Fr. 317.60. Die letzte Betreibung (Zahlungsbefehl vom 19. April 2006) in O._ - und nicht an seinem Wohnsitz in L._ - sei unstatthaft und wider besseres Wissen am falschen Ort erfolgt. Soweit die Vorinstanz erwäge, er habe seine Mitteilungspflicht verletzt, sei dies aktenwidrig, da sich sein Wohnsitz ohne Unterbruch in L._ befunden habe. Er bestreite, überhaupt gemahnt und betrieben worden zu sein. Weiter könne aus den sich bei den Akten befindlichen Kopien der ersten und zweiten Mahnungen nicht geschlossen werden, dass diese tatsächlich versandt worden seien. Schliesslich wiederholt er seine bereits im vorinstanzlichen Verfahren erhobenen Rügen, die die Eingaben der Beschwerdegegnerin unterzeichnenden Personen seien nicht bevollmächtigt.
5. 5.1 Soweit der Beschwerdeführer die Ansicht vertritt, mit der Einzahlung von Fr. 1'089.- am 29. April 2005 seinen Zahlungsverpflichtungen vollständig nachgekommen zu sein, indem er die von der Beschwerdegegnerin aufgelisteten Forderungen (gemäss Abrechnung vom 26. April 2005) mit Ausnahme der Mahn- und Betreibungsspesen (Fr. 118.-) beglichen habe, kann ihm nicht gefolgt werden. Zunächst unterlief ihm offensichtlich ein Versehen, indem er den offenen Forderungsbetrag auf Fr. 1'207.05, statt Fr. 1'279.05, bezifferte. Seine Überweisung vermochte bereits aus diesem Grund die Forderungen der Versicherung nicht vollständig zu decken. Nach den zutreffenden Erwägungen der Vorinstanz enthielt die Abrechnung vom 26. April 2005 auch keinen "Gesamtsaldo", dessen Begleichung sämtliche offenen Forderungen der Beschwerdegegnerin gedeckt hätte. Insbesondere war die Anteilsrechnung in Höhe von Fr. 317.60 - mangels Fälligkeit - darin nicht enthalten. Bestand und Höhe der Anteilsrechnung Nr. 049127015 sind unbestritten geblieben. Dass die Beschwerdegegnerin mit der am 29. April 2005 veranlassten Zahlung des Versicherten zunächst die bereits am 31. März 2005 fällig gewordene Anteilsrechnung Nr. 051073901 deckte, ist nicht zu beanstanden. Sowohl die Restanz der April-Prämie (Fr. 180.05) wie auch der Selbstbehalt von Fr. 317.60 wurden somit zu Recht gemahnt und betrieben.
5.2 Die Vorbringen des Versicherten, er habe die Mahnungen der Beschwerdegegnerin nie erhalten, zudem sei die Betreibung der am 21. Februar 2005 fakturierten Kostenbeteiligung (Fr. 317.60) und April-Prämie 2005 (Restbetrag von Fr. 180.05) - wie bereits diejenige der Prämie Mai 2004 - nichtig, weil sie nicht an seinem Wohnsitz eingeleitet worden wäre, sind ebenfalls unbegründet. In Würdigung, dass der Beschwerdeführer unmittelbar nach Zustellung der Mahnung vom 20. April 2005 - mit Faxschreiben vom 25. und 26. April 2005 - die Beschwerdegegnerin um weitere Erläuterungen zu den offenen Forderungen gebeten hatte und er, obwohl ihm als Rechtsanwalt die Bedeutung der fehlenden Zustellung ohne Weiteres bewusst sein musste, diese erstmals im vorinstanzlichen Beschwerdeverfahren geltend gemacht hatte, ist das kantonale Gericht zu Recht von einer blossen Schutzbehauptung ausgegangen. Folglich hat es auch kein Bundesrecht verletzt, indem es erwog, die Mahnungen seien mit überwiegender Wahrscheinlichkeit zugestellt worden (Urteile des Eidg. Versicherungsgerichtes H 219/82 vom 28. September 1983 E. 1b, publiziert in: ZAK 1984 S. 123 und H 45/04 vom 13. September 2004 E. 2). Schliesslich hat die Vorinstanz (in tatsächlicher Hinsicht) zu Recht festgehalten, dass der Versicherte seinen Wohnsitz von L._ nach O._ verlegte, ohne dies der Beschwerdegegnerin (fristgerecht) mitzuteilen (zur Zuständigkeit und zur Prüfungspflicht der Betreibungsbehörde bei der Bestimmung des Betreibungsortes vgl. <ref-ruling> E. 1a S. 111 f.). Für einen von den Angaben der Beschwerdegegnerin abweichenden Wohnsitz wäre der Beschwerdeführer im Übrigen selbst beweispflichtig gewesen (Schmid, in: Staehlin/Bauer/ Staehlin, Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, SchKG I [Art. 1-87], Basel/Genf/München 1998, N 51 zu Art. 46; Urteil des Bundesgerichtes 7B.241/2005 vom 6. März 2006 E. 3.2). Damit sind auch die Kosten für die Mahnungen vom 21. Juni 2006 (2 x Fr. 15.-) sowie die Dossiereröffnungskosten (Fr. 35.-) und Zustellkosten (für die Betreibung in L._; Fr. 50.-) gerechtfertigt, weshalb der in Betreibung gesetzte Betrag von Total Fr. 612.65 (welcher sich nebst den eben erwähnten Kosten aus dem Restbetrag der Prämie April 2005 [Fr. 180.05] sowie dem Selbstbehalt [Fr. 317.60] zusammensetzt) nicht zu beanstanden ist.
5.3 Das Argument der fehlenden Vertretungsmacht der die Eingaben der Beschwerdegegnerin unterzeichnenden Personen hat die Vorinstanz mit zutreffender Begründung, der das Bundesgericht nichts anzufügen hat, entkräftet. Darauf wird verwiesen (Art. 36a Abs. 3 2. Satz OG).
6. Die offensichtlich unbegründete Verwaltungsgerichtsbeschwerde wird im Verfahren nach Art. 36a OG und ohne Schriftenwechsel erledigt (Art. 110 Abs. 1 OG).
Soweit Prämienforderungen betreffend, ist das letztinstanzliche Verfahren, da keine Versicherungsleistungen im Streit liegen (E. 2), kostenpflichtig (Art. 134 OG e contrario).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 200.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Graubünden und dem Bundesamt für Gesundheit zugestellt.
Luzern, 3. Dezember 2007
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle