Parece que o que descrevi na pergunta foi um artefato de algumas de nossas máquinas ou as versões recentes do UltraVNC melhoraram.
De qualquer forma: Atualmente estou usando o UltraVNC X64 1.0.9.6.2 e ele funciona decentemente nas minhas / nossas máquinas Windows 7. Quando alguém se conecta, o Windows é alternado do Aero para o modo básico, mas tudo parece funcionar bem.
Ah, e a versão agora paga do RealVNC alega suporte total ao Win7 (seja lá o que for ), mas eu nunca tentei fazê-lo.