Opinions vary widely as to whether registry cleaners are recommended for Windows 7 so hold on with that.
I would download and install Revo Uninstaller. Run that and see if there are any traces of your Batman install left and remove them.
Isn't it likely that the date in system restore is when you first installed Batman AA?
If it is, or is before you installed the game go ahead and restore to then.
It might help if you filled out your full specs.
Hope this helps, john
In your first post you mentioned ccleaner. That includes a registry cleaner which I've often used without problem.