How come the unix locate command still shows files/folders that aren't there any more?

You've got the right idea: locate uses a database called 'locatedb'. It's normally updated by system cron jobs (not sure which on OS X); you can force an update with the updatedb command. See http://linux-sxs.org/utilities/updatedb.html among others.

Also, if you don't find files which you expect to, note this important caveat from the BUGS section of OSX' locate(1) man-page:

The locate database is typically built by user ''nobody'' and the locate.updatedb(8) utility skips directories which are not readable for user ''nobody'', group ''nobody'', or world. For example, if your HOME directory is not world-readable, none of your files are in the database.

The other answers are correct about needing to update the locate database. I've got this alias to update my locate DB:

alias update_locate='sudo /usr/libexec/locate.updatedb'

I actually don't use locate all that much anymore now that I've found mdfind. It uses the spotlight file index which OSX is much better at keeping up to date compared to the locatedb. It also has quite a bit more power in what it can search from the command line.

Indeed the locate command searches through an index, that's why it's pretty fast.The index is generated by the updatedb command, which is usually run as a nightlyor weekly job.

So to update it manually, just run updatedb.