I honestly don't know. I've never personally encountered a server whose only way of handling sessions was via memcache storage, let alone whose own server configuration just automatically breaks the first time it tries to even USE it's own configured settings.

Start by telling them exactly what you told us here. It's their server. They're the experts on how they configured the server. And since it's a non-traditional configuration, they're gonna have to be the ones to fix it because they're the ones who know why they configured the server that way in the first place. They probably set something up for one specific customer's needs and don't even know they're causing problems to customers like yourself because they've done it in a way that's globally affecting everyone instead of just that one customer. Or maybe it's worse than that. Again, only they will know.

If they can't fix it, try another host who uses a normal configuration.