Hi Heat,
My company used to use WebAfrica's hosting solutions in the past. We had our own server, that hosted all our websites, even the D.B driven ones. We had direct RDP access to the server, so we could do what we wanted, WebAfrica made sure regular backups of the server were taken, updates installed, etc. If I remember correctly we loaded up our own SQL Server version because if they have to do it, (i.e. carry licencing costs), they charge you extra per month. Another good place to look at is Absol (http://www.absol.co.za) and GamCo (http://www.gam.co.za/)
Is this what you're talking about?
The Question is the Answer, and the Answer is the Question!