If I spider your site I'm not seeing any /index.php urls. Does that mean you did get Joomla to cooperate with your rewriting?

Or was your problem that you'd previously had urls indexed with /index.php/ paths and you needed to remove them?

Couldn't you rewrite those /index.php/ urls to remove the /index.php/?

Like this in .htaccess:

RewriteRule ^(.*)$ /index.php/$1 [L]

Only used Joomla once, but there must be a way to configure joomla to just use "/" instead of "/index.php/"?

Update:

Here's a solution to your /index.php/ issue:

http://www.eprcreations.com/remove-index-php-from-joomla-urls/

Once you've updated that, and have your urls working properly without the /index.php/, you could add this slight modification of the rewrite rule above so that all your old /index.php/ urls would be 301'd to your new ones:

RewriteRule ^(.*)$ /index.php/$1 [R=301,L]

Put it underneath the RewriteBase / line they describe in that post.