Hi Matthias,
Unfortunately we cannot control trust level by web.config or user.config, if the host is using medium trust it is medium trust and nothing can change it. Look under Administration > System Information
Does it say Full Trust there or Partial Trust?
VirtualPathProviders do not work under .NET 3.5 Medium Trust which means it cannot load the theme.skin file from the skin folder. You would need to copy it from the skin folder into /App_Themes/Default
This means in a multi site installation all sites will use the same theme.skin file which can be a problem if they need different settings.
I recommend everyone to use .NET 4 hosting because even with medium trust the VirtualPathProvider can work under .NET 4
See also the notes at the bottom of the page Understanding the theme.skin file
Another good reason to change to .NET 4 is because when .NET 4.5 ships later this year we will most likely drop support for .NET 3.5 and support only .NET 4 and .NET 4.5.
Hope that helps,
Joe