I`ve updated to version 9 but if I remember rightly try this.
Delete all the albums from the media library tab. Highlight each one and right click then delete.(If you get the option in V8 DON`T DELETE THEM FROM THE COMPUTER AS WELL)
Simply do your search as before and refresh your titles.