Webhosting for WPMU

I've been told on several occasions that shared hosting is not recommended for WPMU -- especially when trying to use the multi-db code that you guys provide.

My question is: What is the best (and cheapest) option for hosting that you would recommend?

I see that you recommend psek.com and they have a hosting package for $7/month. Would that work?