If you were using the client's own functionality to do this before you did so manually was there enough space for a full copy of the data on the source drive? The client doesn't do some things in the best ways, and could actually be creating a temporary copy while moving the data, though IDK and can't test as I don't have an external right now. The trick you found is one of the manual forms of moving installed Steam apps from before they finally added this feature to the client itself.
The files not being removed on uninstall is very strange, but could theoretically be caused by having two separate appmanifest files for one app in two different Steam Library Folders. The appmanifests tell Steam that a game is installed in a Steam Library's
/steamapps/common folder, and without them it doesn't recognize that the game is installed but with one it will act as if the game is installed right up until it gives you a "missing executable" error. It's not possible to install a game that's already installed to a different Steam Library Folder of the same client though, so I'm guessing it was caused by manually copying or an installation from another machine which was put on the external drive. I suspect that Steam would consider the last loaded version to be the valid one as the Steam Library Folders are indexed internally with 0 being the default and 1 or higher being custom ones. If you remember whether it was the default or a custom folder can you please share which it was? :P
"Verify Game Cache" is only meant to check your local installation of a game and ensure it's not corrupted and has no power over the Steam client. If you believe the client is corrupted the best way to fix that is to uninstall and reinstall Steam, but you could try a Steam client clean up: Windows, Mac (based on Windows directions). This is like a soft-reinstall of Steam and will not destroy installed games, plus will only lose some Steam client settings; it can leave some corrupt data behind though. A hard uninstall/reinstall of Steam following the official directions is far more likely to fix issues, but will lose most of your settings including non-Steam shortcuts and save data which failed to be synched with the Steam Cloud.
Finally, that manual moving method can fail if the game has an update newer than the version that you have installed, or for other reasons that seem to basically be "because Steam felt like it". The easiest way around this is to also copy or move the
appmanifest_#.acf (where # is the unique appid of an app on Steam) file(s) from the
steamapps folder when you're manually moving installed Steam apps as this keeps the current installed version data. Sometimes though this also has a problem, so it's best to know about and try both methods. Moving or deleting an appmanifest will also have the benefit of "uninstall"-ing the game (as far as Steam is concerned) as mentioned above.
I tried experimenting to get around the problems moving some games (most are fine) by playing with the appmanifest files values, but from what I remember of my tests when it did have an issue it was persistent. This lead me to believe it's caused by encrypted data such as part of Steam's DRM known as Custom Executable Generation which encrypts a games executable based on the owner who installed the game, and I think can also go further but I'm no Steam dev/expert.
If you try any of the above make sure to completely close the Steam client before saving any changes to it's files. Not only will it overwrite most changes using it's known data anyways when it closes, but it could also cause problems.