You didn't actually describe where you moved
them to, and how you did it. As for the locate,
that will be fixed on the next reboot or so ;)
Or run updatedb manually. It doesn't keep
track of files over times, it takes snapshots.
Please read one of my all-time favourites