I think I redeemed a code for this game a few months ago, but it's not in my iTunes library. I would download it again, but if I never actually redeemed the code in the first place then I would be charged. Is there a way to check if I ever downloaded it without going through my account's entire purchase history?
To to the game's page in iTunes and try to write a review. It it lets you, you own the game and can re-download it for free.
An easy way to check is to click on the stars to leave a review. If it will let you do that, you own the game. If not, it will tell you that you must own the game to leave a review. I own and delete so many games, this is a quick way to find out without paying.