I would highly recommend user-mode linux (UML) hosting, like bytemark or Linode: http://user-mode-linux.sourceforge.net/uses.html
Starting around the same price as average shared hosting, you get your own virtual linux box (i recommend debian), on which you can install java, mod_python, php, mono, jabber, or whatever you need. You are no longer subject to the whims of the hosting provider, with respect to things like which version of PHP they support, or how many mysql databases you can create. -- http://mail.python.org/mailman/listinfo/python-list