I don't think there is a way to recover a lost phone , if you didn't install an application on it before it's lost .
There's an application called FindMyiPhone on iTunes , by Apple.It does exactly what you said :
register the Iphone on Itunes then be able to track it
To use it ,you need to register an account using an iPhone 4 (mobileme account) and you need an iphone 3G or 3GS or iPhone 4 (for GPS tracking , since iPhone 2G has no GPS).
Check this link :
http://www.apple.com/iphone/find-my-iphone-setup/
Find My iPhone will pinpoint the iPhone’s current location using Google Maps and let owners send and display a message on the iPhone even if it’s locked, presumably to provide information on how to return the phone to the finder of the phone. The Find My iPhone feature can also force the iPhone to play a sound for 2 minutes, which is useful for not only getting the attention of the finder of iPhone but also locating it between couch cushions.
P.S : If you have a jailbroken device and don't want to use FindMyiPhone , I think that this link might be interesting :
http://techpp.com/2009/09/18/6-ways-to-find-track-lost-stolen-iphone-free/