The phone home is an option (is there any software that already does this?) but someone could just reformat and get around it. There's lots of companies and shareware authors offering 'phone home' solutions, but most of them are just a background program that is easily disabled. However these two claim to survive a reformat and reinstall by hiding themselves in odd places on the hard drive.
http://www.laptopretriever.com/http://www.ztrace.com/Unfortunately none of these companies seem keen on offering any real technical detail of how their system works, so it's difficult to know how true their claims are.
Phoenix have a system called TheftGuard that sits in the BIOS, but you'd have to buy a PC that supports it and it tends to be aimed at laptops.