The reason why you can't find the .deb file in the /var/cache/apt/archives/ directory is because it isn't there anymore.
The locate command finds it because locate does not look at the actual directory contents but works from a cache.
From man locate:
locate reads one or more databases prepared by updatedb(8) and writes file names matching at least one of the PATTERNs to standard output, one per line.
By default, locate does not check whether files found in database still exist (but it does require all parent directories to exist if the database was built with --require-visibility no). locate can never report files created after the most recent update of the relevant data‐base.
To update the database cache, run this command:
sudo updatedb
updatedb creates or updates a database used by locate(1). If the database already exists, its data is reused to avoid rereading directories that have not changed.
This should sort out the locate command finding files that no longer exist.
EDIT
For the /var/cache/apt/archives/ files not existing, maybe you run a clean command after running the sudo apt-get dist upgrade command.
Any of these commands will automatically clean out the /var/cache/apt/archives/ directory.
sudo apt-get clean
sudo apt-get autoclean
Source: Cleaning out var/cache/apt