I am searching for a SharePoint (MOSS) hosting that is shared provider that supports deployment of custom solutions (.WSPs) - it would be okay whether it was medium trust. I am creating a public Web page on SP and also the client does not wish to host it or purchase the license all in advance. Any suggestions?

I am unaware of any hosting that is shared plans that offer the deployment of custom solutions. From what I have seen, you'd need a minimum of a semi-devoted hosting plan. I am a developer at Fpweb.internet and that i know that can be done this using some of their semi-devoted plans.

if you're searching to build up a custom Sharepoint Page, you might think about the sharepoint plan at ASPHostPortal.com. They permit not just medium trust, but full trust mode which certainly permit you to produce a custom page via any Sharepoint Designer tool you will probably have.