This might be related to your hosting company server. Who are you hosting with and do you know whether it’s on Windows or Linux servers? It sounds like your websites might be running on Windows Servers which might be causing the problem.
Here is an article that discusses it (Read the section on ‘Permalinks without mod_rewrite’)
“As we run Zeus and not apache for our shared hosting environment there is a limit to what you achieve using htaccess. We allow this to be used to create general password protection and custom error pages on our shared hosting cluster.”
Is this peculiar to Zues? I am considering hosting elsewhere in order to resolve this issue and wondered if you have any experience of TSOHOST who appear to be highly regarded for WordPress hosting.