Maybe check out the offers section of WHT and see what providers are offering. You also may want to search for JSP web hosting providers in Google. That may help you out a bit. Once you have a pretty solid list of providers, send them pre-sales questions and search for reviews. May have to raise your budget a bit.