Patch the game (if you haven't) and in C:\Users\'Your PC Name'\My Documents (the next folder locations are ones I am not too sure of)\WBGames\batman or batman arkham city\bmgame\Config,delete the files bmgame,bmengine and userengine.Start the game,re-configure your graphics settings and post back with your results.I found this via EVGA's forums.All credit goes to them.
Hope this helps.:)
Thanks a lot for the advice. Are you implying that I have to manually patch the steam version of the game? That's the one I have and it is certainly on automatic updates. Do you have to get the patches from Games for Windows Live? I will def try deleting those files though.
How do you know for sure if patches were installed? Where is the indication of that? I don't see anything on the title screen letting me know.