I tried Winhost and had the same issue. I moved to Arvixe
and haven't had any issues with Sitefinity 4 on their environment. Most hosting providers that I looked into had limitations that either restricted the app pool or restricted your trust level and Arvixe
does not. I've been there since April and have had no issues and would recommend their services.
I am a developer and understand hosting so I have not needed their support but I did contact them with some questions and they were very prompt in responding to my inquiries.