Ok, opcję aktualizacji masz zawsze dwie

1. Aktualizacja jako paczka
2. Aktualizacja jako lista
I teraz tak:
ad 1. Aktualizacja jako paczka polegała by na utworzeniu w serwisie paczki plików, które musza zostać zaktualizowane (dobre przy krytycznych aktualizacjach oraz takich gdzie jest dużo zależności). Czyli to w serwisie musi być paczka, program zasysa i podmienia pliki.
ad 2. Aktualizacja jako lista sprowadza się do przechowywania ZAWSZE najnowszych wersji wszystkich używanych plików. Program pobiera listę aktualizacji, lub sprawdza czy jego pliki nie są stare i pobiera te, które wg. siebie potrzebuje.
Obie opcje są tak samo porąbane ;P w 1 musisz generować paczki za to pobranie jest łatwe a w drugiej nie martwisz się paczkami ale za to ciężej znaleźć i zaktualizować wszystkie stare pliki...
Co do samego wersjonowania to zawsze można zrobić to najłatwiej jak się da

Wrzucasz nowy plik do "repozytorium" dostaje on wersję nr 1, nadpisujesz plik - ma już wersję nr 2, znowu nadpisujesz - ma wersję 3 itd... - to jeżeli byś robił według metody 1 gdzie plik to paczka plików.
W drugiej jest ciężej- tak jak wspomniałeś trzeba dać jakieś rozróżniki plików (np crc/md5) albo do aplikacji dołączyć liste plików z ich wersjami. Po aktualizacji lista ta też by się aktualizowała - sprawdzenie nowej listy czy jest taka jak stara nie powinno stanowić problemu.
A teraz moje zdanie - (czytaj jak ja bym to zrobił)

najprościej!

Wrzucam wersję programu do samego programu. Program sprawdza czy jest paczka z wersją wyższą niż ma, pobiera, aktualizuje, aktualizuje swoją wersję i śmiga...
Jeden problem - Aktualizacja może być robiona niezależnie (to znaczy że paczka wersji 1.5.6 ma wszystkie zmiany z wersji poprzednich) lub zależnie (każda paczka ma tylko zmiany w stosunku do poprzedniej wersji - jak mam 1.5.3 to muszę po kolei aktualizować do 1.5.4, 1.5.5 i dopiero 1.5.6) - ja bym stawiał na niezależność

HTH!