Problem:
Ok so you did every thing right and you still can not get Clean URLs (URL rewrite module) to work with the embed of Gallery2.

Here is what finally worked for me:
1) Got to the "URL Rewrite Administration" within Drupal (embed), this is important as some additional embed specific fields will appear.
2) Go to the "Setup" tab and enter a value for "Htaccess path:" pointing to your Drupal install (ex on Windows:  E:\DomZeus\anciensducairecom\wwwroot), not to your G2 folder!

For "Public path:" I just put "/" (my Drupal root)

Additional step if you do not use a .htaccess with Drupal (like me).

3) The previous steps generate a .htaccess file (in the Drupal root). I pretty much copied the URL rewrite rules, from that .htaccess file, to my Apache configuration file where my current Drupal rules are.

Here is what these G2 rules look like:

RewriteCond %{REQUEST_FILENAME} -f [OR]
RewriteCond %{REQUEST_FILENAME} -d [OR]
RewriteCond %{REQUEST_FILENAME} gallery\_remote2\.php
RewriteCond %{REQUEST_FILENAME} !/index\.php$
RewriteRule . - [L]


RewriteCond %{THE_REQUEST} \ /gallery/([^?]+)(\?.|\ .)
RewriteCond %{REQUEST_FILENAME} !/index\.php$
RewriteRule . /index.php?q=gallery&g2_view=core.ShowItem&g2_path=%1 [QSA,L]

Man oh man! Spent nearly all-day on this one....