Just checked it out myself, I never thought to check it on my XP partition! (My PC dual boots Vista and XP).
As you rightly say, the Config folder and the AC_SearchStrings.dat file is present under Windows XP and CCleaner does correctly clear the eMule search history. However, under Windows Vista the situation is quite different as eMule does not install the same files and folders as under XP, that's obviously why it fails to clear eMule's search history on PC's running Vista. It looks like I have flagged up a little bug that ideally needs addressing!
Regards
Rob Mob