Some hosts offer "mixed" environments. By that I mean they may have a farm of windows pcs as well as a farm of Linux like computers. Speak with them about it as an option, also perhaps there is something identifiable in the php settings as seen in the version information that could identify what they are using for caching which appears to be the issue. Ie. Can they disable it or put you in a bank that has it disabled?
Bookmarks