How to redirect URLs with '?' but no query string parameters

[eluser]Unknown[/eluser]
Hi,
I was using Codeigniter for my site which was hosted on GoDaddy earlier. For some reason, the standard CI URLs didn't work as expected.
e.g. - http://domain.com/controller/function/param
Hence I had to update one of the core CI libraries such that it generates URL in the form - http://domain.com/index.php?controller/function/param

Now all the URLs cached in google are in the format mentioned above.
I have now changed the host and also upgraded my CI installation to 2.0.3.
The new host supports standard SEF URLs.
What I need to achieve is get rid of the index.php segment from the URL which can be easily done using htaccess. Though I need to ensure that all the google cached URLs redirect to corresponding new URLs without index.php? segment. For example -

http://domain.com/index.php?album redirects to
http://domain.com/album

Can anyone please help me out with it?

Regards,
shreyas.ab