Clean URLs not working properly with Firefox and Opera!

I am having a problem with clean URLs not working properly. Neither my host's tech support, no the falks in the forums here were able to figure it out, so I took the liberty of posting it here. After weeks of searching and trying I really believe it is a bug and belongs in this section.

The problem is this:
I do a fresh installation of Drupal 4.6.3, and everything works "out of the box", i.e. I DO NOT change anything in any of the files except for the $db_url and $base_url in sites/default/settings.php per default installation instructions. I am using shared hosting, but I am allowed my .htaccess files, and mode_rewrite is enabled.

When my site is up, the first and only thing I do after registering the first user is go to the "administer - settings" page and change the "name" in "General settings" from 'drupal' to, say, 'test'. I click the "save configuration" button and the title of the site changes to 'test' as expected. I can also change other settings on this page in the similar manner.

However, as soon as I enable "Clean URLs", all the settings jump back to the default values, i.e. the name of the site is 'drupal' again. While "Clean URLs" are enabled, I cannot make any changes on this page - the settings jump back to the default values silently as soon as I hit the "save configuration" button. I do not get amy error messages in either drupal's or server's logs - I think that alone qualifies it for a bug.

If I turn "Clean URLs" back off, I again can make changes in the settings page, but the story repeats as soon as I enable the "Clean URLs" again...

The clean URLs themself look fine during the whole thing, and I can browse the site as well. Also, this problem shows up with Firefox and Opera in Windows, but not with IE. This has something to do with my host as well, since on my other host the exact same installation worked flawlessly. Both hosts have Apache.

I would REALLY REALLY appreciate any help on this matter!