I have had a chance to test a couple of shared hosts. Unfortunately at this stage for all concerned they are both Australian hosts, I haven't had an opportunity to test any US servers yet. I have had mixed results.
The first was StudioCoast
who I had no issues with whatsoever and they happily added the template mapping for me.
The second was ExpressNet
who have been extremely helpful with me on this, they allowed me to run my site in Full Trust but at their default which is Medium trust it doesn't work at all I just get a Security Exception. They were asking is there any work around that could be implemented so that we could get it to work under Medium trust, you said that already there is none at this stage but I thought I would double check.
If you have time could you explain what it is the Sitefinity uses that breaks this trust? It would just be helpful to know this information to help the hosts understand that your application is safe on Full Trust?