I'd be interested at prompting others about this; those who have downloaded SilverStripe and got it going on their webhosts. We run our own boxes, which means we run whatever Debian (Etch) is up to, currently 5.2.0.
You have inspired me to contact some NZ hosts, given this was a topic on the NZ PHP Group a few weeks back, and I didn't see anyone shout out and say a domestic webfarm style (under $30/month) business provided PHP5 hosting. It seems to something that premium hosting companies (e.g. $100+ a month) provide (there are a few of these, including ourselves), from what I can tell.
I see http://www.a2hosting.com (international) being mentioned a bit, and this provides PHP 5.2.1 currently, as well as subversion, ruby on rails etc, so these guys are obviously providing a decent service rather than lazing about with draconian server software versions.