I just paid for another six months hosting with AVS Networks, the Australian web-hosting company who provide the hardware and bandwidth that makes The Fishbowl work. (This also marks six months since I switched from being an early adopter of Radio Userland 8, and became a Movable Type latecomer.)
The quality of a web-host is measured by how little you notice they exist, and in the six months I've been running The Fishbowl on their service, I've noticed them precisely once. That's a pretty good record by any account. Good work, AVS.
I wanted to check out AVS on your recommendation, but the link to their site is timing out. Pity.
Oops. I think the URL I linked to was obselete. Changing .net.au to .com.au seems to have made it load again.
I'd recommend SuppleHost (http://www.supplehost.com/index.jsp). For $18/mo. I get a private JVM, Java 1.4.1, the latest Tomcat support and much more. If anything, they're worth a look.
That and they are VERY good about support and understand when you talk to them about technical issues.