Você diz que o servidor de e-mail pode lidar com dezenas de milhares de usuários por servidor de intervalo médio, mas isso não é estritamente verdadeiro. Claro que um simples servidor postfix com acesso POP 3 pode lidar com isso, mas tudo o que faz é enviar e-mail. Se você quiser dar uma olhada em coisas como calendário, contatos, documentos compartilhados, etc, de repente você tem um servidor Exchange e pode armazenar substancialmente menos usuários por servidor.
É a mesma coisa com o Wave, você está recebendo e-mails e enviando muitas outras coisas para ele, então com certeza ele não suportará dezenas de milhares de usuários por servidor, mas você pode fazer muito mais com isto. Então, sim, eu imagino que vai precisar de mais recursos do que um simples servidor de e-mail. O Java pode ter sido mais rápido, mas ainda é muito robusto, então o seu servidor Wave nunca será capaz de suportar dezenas de milhares de usuários, provavelmente muito menos, mas se você quiser os recursos, provavelmente valerá a pena.
Eu suspeitava que um servidor de ondas pequenas rodaria em um VPS razoavelmente determinado, provavelmente vai ter muita fome de memória, então não deixe de dar bastante. Infelizmente, o Google não divulgou muita informação, por isso vai ser um caso de experimentá-lo e ver.