As I understand it, no competent and responsible shared hosting provider should provide full trust.
However, a virtual private server might be your answer. You might want to take a look at http://www.jodohost.com and see their Windows VPS packages. I haven't tried it myself but I have a reseller account with them for shared hosting which I use for a DotNetNuke site and a few other things. I'm very happy with their service. They really do seem to know what they're doing which is in stark contrast to many low cost hosts I've used over the last 10 years or so.
They seem to be breaking some new ground with the Windows VPS. For $49.95 / mo you get what looks and feels like your own Windows 2003 machine with admin access. You also get access to a shared SQL Server on another machine. Most Windows VPS's I've seen advertised don't give you SQL Server and if you buy a package with enough memory to realistically install SQL Server yourself then the price is such that you may as well go for a dedicated machine.
I know that sounds like an advertisement but I really am just a happy customer.
Anyway ... I think your choice is either something like that or a dedicated machine.
Cheers
Ross
Copyright (c) Marimer LLC