Should i have the app store in a
database the udid of each device that
it is installed in and when launched
check that?
Something like that - you can't persist data on the device after an uninstall. So the data you want to maintain needs to be on a server (or something similar).
Possibly you have a remote store, that has a table of UUIDs and a list of all the IAPed items they've bought. When the device exec's the application, make a call to the server to see if you need to pull down the items.
You can make it better by having a bit you toggle, so on first run you make the call, on all subsequent runs you don't (you toggled the bit off). That way your not making the call every app startup.
So on that first call, you hit the server and enumerate any IAPed the client has purchased, and push them down to the phone. Happy customer!