I've had a few "where the hell is that" moments in my time. My usual way to tackle is as follows.
The first thing I do is browse the C: drive (
\\LOSTCMPUTER\C$) and look at the local profiles to see if I can hopefully determine at least what department it resides in. Then poke around in the profile directories to try and find files recently changed and contact the user if anything looks promising. If not, wander around the department and tie up all computers you think are there and what is actually there.
Failing that, in the global logon script, put something like this.
if($ThisComputerName == 'LOSTCOMPUTER')
WriteFile("\\SERVER\WRITEABLESHARE", "$Username logged onto LOSTCOMPUTER");
Other things to try might be to disable the computer object and when someone phones asking why they can't log on to the computer, note where it is and re-enable the account.