Any non-301 response would seem to be physically impossible.
Have you run a header check to make sure they really serve a 301 and not a 302?
'Back in the day' of the '302 Bug' one huge issue that forced webmasters to install their own redirects via .htaccess and likely helped prompt Google (and Yahoo!) to 'break protocol' and treat 302s much closer to 301s is hosting company redirects have always leaned toward using 302s, so you could actually 'hijack your own site' unintentionally unless you installed your own .htaccess redirects AND backed any set via control panel out of their system.
But, as far as hosts go, since they don't know whether the redirect is permanent or temporary, because it's 'not their site or decision', it's really the 'most correct' option for them to use, so that's still (afaik) what many 'stick with' when you redirect via the control panel or something similar.
There were even cases where if you didn't hand code the redirects yourself you could end up with a 302 you thought you 'set in the system' as a 301, and until the ability to hijack site's rankings in search engines was discovered, it really wasn't a big deal...
Anyway, you might just want to double check and make sure the response is really a 301 if you're relying on the host to 'get it right', because even though they've gotten better, they totally sucked for a long time when it came to actually sending a 301 redirect.