I guess it depends on the circumstances of how the key was stolen.  If the
key was stolen out of your home, or with any ID, or if there is any way
the thief can know where you live or where you park you car during the day
(work, etc.), you should have the locks on the car recored and new keys
made, and the keyless entry coded changed.  If you do not do this, the
theif can come back anytime he wants, and steal you car.  He can even
wander a parking lot or neighborhood pressing the "lock" button on the FOB
until your car beeps it's location.  

It's no accident he stole your car key.  Thieves target car and even house
keys for just this purpose.  

New keys are $80 each, new cores $50 and new codes another $50, so you are
looking at $500 total.  Take it to the dealer and have it done right.

If the key was stolen in such a way that the thief could never, ever, ever
know who you are, where you live or where you normally park, then you
might take the risk and just get a replacement key.

However, if he took they key, it propbably means he did so knowing he
could find the car later on.

J

Take the car to the dealer and have a new key cut and when they go and
reprogram the memory they will delete the key that was stole.  your
problem is solved.  The key will allow them access but the car will not
start.