The software was indeed removed. A bug in the "Install Mac OS" application causes the installed correctly message to appear. If you remove the software using the Mac OS 7.6 Installer (found in the Software Installers folder in the Mac OS 7.6 folder on the Mac OS 7.6 CD-ROM), you will receive the correct message when you custom remove software.
This article was published in the 3 March 1997 "Information Alley."