Could it be possible that updatedb does not start at every launch of the system. My question could seem strange, but on a laptop, it consumes a lot of power to update the database every launch when working on batteries. There's maybe already a way to run updatedb manualy and not automagically.
updatedb (as a part of slocate) is made to run as a cronjob by default. Remove slocate from /etc/cron.daily/ and it won't run at every launch. To run it manually you just run "updatedb"
see what Patrick said.
