MapYourValentine from Google – “sometimes, what means the most isn’t something. It’s somewhere.”
Update: to avoid confusing your Valentine, you might want to use the ‘preview’ feature before sending. I just tested the site on myself using ‘Kedainiai, Lithuania’ as my special location and in return I got a Valentine’s Day message with a cute little heart circling a spot in the middle of the Caribbean Sea!