Dababase Rebuild Utility
Do you have songs that are still showing up after deleting them from the database? You can try running the Rebuild Search Keys from the Profiles>Utilities menu to see if that fixes it, but we have not seen an issue where deleted songs still show in your database before. If you can get a screen capture of that happening, we would love to see it.
My song database is huge. There used to be a Rebuild Utility that got rid of "deleted" songs, but I can't find it in version 7.