Hi,
I'd recommend SL Host - their VPS
Great support: YES
Wildcard DNS: YES (although you may have to ask that it be 'turned on')
Mu works there out of the box: YES
In fact, they've been running a great 40% off deal for LIFE if you go with 1-year. 30-day guarantee still applies.
For managed VPS with Cpanel, I've not found a better price. I have 2 VPS accounts there myself. Using this link to VPS Hosting will take you direct to current special discounts. Then just click the plan to see the ACTUAL discounted offer. I will receive credit against my own hosting fees there should you decide to grab an account yourself while sale is on.
If only my current job for WPmu installation could have been on my servers at SL Host, rather than at RackSpace running Plesk. I'll be posting my cheat sheet for Plesk install here shortly. Just waiting for my partner in France to send me HIS record of Plesk tweaks to add to mine.
Deb