I usually use 1and1 1and1. They are one of the largest in the world and their $4 a month plans cover everything you need for a small store. They support just about everything on that plan... adding an ssl certificate is another $50 a year if you are doing eCommerce.
They are so large they usually have encountered everything before so their machines are well configured to handle most anything. Probably a long wait to get someone on the phone if you need to, but I don't think I've ever needed to call when using them.
Maybe wait until our support gets back to you... I'd hate to have you switch hosts and find that we really did have a bug. I just haven't heard of it and it doesn't make much sense to me that it would be a bug in the software and nobody has reported it that I know of. If it does happen to be our bug, they actually gave the correct response... I just don't see how it could happen and us not know about it, but I've been wrong before (I think... I'd have to do a search of the forum to be sure).