For a long time now I have struggled with removing index.php from my EE websites. I have used a mix bag of the include/exclude method and add-ons that deal with making the include/exclude method easier.
A few weeks ago I was having some issues while creating a multi-language site and Jack McDade sent me a snippet of .htaccess code that has worked on several hosts (including a dedicated mac mini, gatorhost) and is simple. I asked Jack's permission to post the code and he said yes. So if you find this handy make sure to give him a thanks by purchasing one of his many add-ons or follow on the twitters...
AcceptPathInfo On
Options -Indexes
RewriteEngine On
# Looks for files and directories that do not exist
# and provide the segments to the index.php file
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond $1 !^/index.php
RewriteCond $1 !.(css|js|png|jpe?g|gif|ico)$ [NC]
RewriteRule ^(.*)$ index.php/$1 [L]