Pra começar, o Java só roda em um “jailbroken” iPhone*, já que ele viola os princípios comerciais da Apple, por permitir que qualquer programador lance uma aplicação sem passar pelo aval da Apple.
Isto posto, você vai ter várias dificuldades se quiser atingir TODAS as plataformas que você listou.
Normalmente sistemas comerciais costumam limitar-se a apenas poucos tipos de celulares (aqueles que têm hardware e software suficiente para poder rodar o tipo de aplicações que você quer), e são testados para cada plataforma e tipo de celular.
Normalmente, sem precisar instalar nada fora seu sistema (é claro que você pode pagar alguma coisa para poder usar uma JVM no Windows Mobile ou Phone, por exemplo, ou então no Palm OS, mas acho que náo é esse o seu caso):
em iPhone - usar Objective-C++
em Symbian - você pode usar Java, ou então C++ com Qt
em Brew - C++ (acho que alguns telefones Brew rodam Java também)
em Windows Mobile e Windows Phone - aconselha-se usar o C# para rodar no .NET Compact Framework
em Android - Java na veia
no Palm OS - não sei bem
- Jailbroken: Palavra bonita para “destravado”, mais ou menos como se fosse um Playstation II destravado. Ou seja, a garantia vai pro espaço, entre outras coisas, o que normalmente não é aceitável em ambiente empresarial.