Windows サービス絡みで Windows Server 2003 と Windows Server 2008 との違いだと、Session 0 分離か UAC 絡みが疑わしいように思います。
次のような手順で切り分けられるのではないかと思います。
Session 0 分離の可能性:
・Windows Server 2003 の端末上でログオンして、サービスを起動&終了 (これはできているようですね。)
・ログオンした状態のまま、同じ端末上で別のユーザーでログオンする。(別のログオン セッションを立ち上げる。)
・最初にログオンしていたユーザーはログオフする。
・あとからログオンしたユーザーのセッションで、サービスを起動&終了してみる。
=> Windows Server 2008 の Session 0 分離を疑似的に実現できるはずなので、これで実行できなかったら Session 0 分離の影響です。
セッション 0 の分離 - Windows 7 対応アプリケーションの互換性
http://msdn.microsoft.com/ja-jp/windows/dd871151.aspx
UAC の可能性:
・Windows Server 2008 の端末上でログオンして、サービスを単体のアプリケーションとして実行してみる。(これはできているようですね。)
・次に同じ端末に別のユーザー(同じ権限を持つ人)でログオンする。(元のユーザーはログオフしても構わないと思います。)
・同じくサービスを単体のアプリケーションとして実行してみる。
=> VB アプリのインストールが正しくない可能性が高いです。VB アプリのインストールを管理者として実行していないために、必要なコンポーネントやレジストリが仮想化されてしまっているとか。
ユーザー アカウント制御 (UAC: User Account Control) - Windows 7 対応アプリケーションの互換性
http://msdn.microsoft.com/ja-jp/windows/dd883236.aspx