I've tested Indexmenu using both the "Dokuwiki Internal" and the ".htaccess" settings, both with and without "Use slash as namespace separator in URLs". The site is running on a Centos server with apache. I have not had any problems with Indexmenu and nice urls. Here is the url using "slash as namespace separator" and ".htaccess":
http://mturner.org/xen_server/
As you can see, indexmenu gives nice urls. So the problem is probably with the way Nginx handles re-writes.
A quick google shows that Nginx does not conform to the apache uses of CGI, and since the Dokuwiki Internal method is tied into the way in which apache handles CGI scripts, that method would probably not work (but this is just a guess)..