There is a sepparate code for HU and another one for CD changer.
You need the HU code after you deattach the battery, and the CD code ONLY when you deattach the CD from HU...if you deattached the battery only, or took off the whole thing but havent deattached CD from HU, you will not be asked for CD code.
I have a "SEARCH" problem when I try to take out the disc and it gets stucked, this stucking also happens when I try to change 2 CDs that are allready inside...
So I think your CD is not getting all the way inside in it's place.
After all, my car is 2001, yours..99 right? And it's abbout time to change the rubber things (dont know the word) and do some cleaning