I have two domains setup on my linux box. Normal permalinks works on one, but not the other. The second domain works if I use the /index.php/ permalink.
phpinfo reports the same on both, mod_rewrite is enabled. htaccess exists is set 666 and gets populated when I update the structures, but apache throws 404's on the second domain.
I even tried copying the htacces from one domain to the other.
The Vhosts file info is the same for the 2 doamins except for the domain names and physical locations for the files (document root, logs, etc).
I have a phpinfo script on each domain. Here are the links.