MOSSHosting, Rackspace, and FpWeb are all capable hosters - hopefully you can work out a plan that works.
The thing that makes MOSS hosting with SharePoint Server 2007 is that the web applications share execution space, and just as Aaron answered, deployed code for one application can affect another, peer application. There aren't sufficient security barriers between applications so to do it right, each MOSS hosted application could require its own instance of MOSS. Lots of admin time, relative to configuring WSS, for example, which can be replicated at low cost, causes prices to be higher.
Most, if not all, of these vendors have virtual hosting offers, which can help with the price.
If you can, though, look for a hoster who is now providing support for SharePoint 2010. SharePoint Server 2010 is architected with support for multiple tenants, and hosting in this type of scenario is fully supported.
Happy Hosting with SharePoint 2010!
Owen