Best is to host Silverstripe on a VPS with enough memory assigned. Shared hosting often doesnt provide you with the options to add more memory in php.ini Also you can install cache extensions which speed up silverstripe on your VPS like xcache.

great thread -- is there / or could this be a doc on the site?

just posting my own hosting experiences, mostly with shared hosting and silverstripe:

good:
hostmonster.com - have stayed with them as much as I can, great support, and I havent had any silverstripe problems,
godaddy - have worked for me with silverstripe,

problems:
canadianwebhosting (vps) - got silverstripe to work after support fixed a bunch of server settings,
1and1 - absolutely terrible, they run php4 as standard , and you set php5 in the htaccess , and silverstripe cannot (my own conclusion) work, you get a 500 internal server error however you try and do it, support is terrible as well,
sibername - havent run silverstripe on them, but they were down a lot so I quit with them, they may have improved though.

soso:
hostpapa - havent tried silverstripe with them, they will nickel and dime you, and they make it hard for you to leave.
123ehost - just one silverstripe site hosted with them and it works so far,

I host my SS sites on Media Temple whenever possible. Their Grid Service plan can run SS, albeit a little slowly, so that plan's only really useful for testing, development and small SS sites. However I run production and medium-large SS sites on their Dedicated Virtual plan, which has plenty of oomph for running SS. One of my clients, Regal Models, runs their network of model sites and their main website on a single Media Temple DV server. No problems whatsoever and usage actually has barely gone over 5-10% of server resources so far, and we're getting monthly traffic in the five figures (each site, not total).

So.. a big thumbs-up for Media Temple and their dedicated plans!

I use it in Russia, in Moscow on rented hosting server.