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. 