Have you tried doing an "rpm --rebuilddb" as root? I tried that before and after deleting the /var/adm/YaST/InstSrcManager/ files since it seemed like the rpm database was corrupt... except that apt/synaptic and kpackage appeared to work fine.
I'm leary of doing rpm --rebuilddb since I'm not sure what it does and I suspect the rpm database is OK.
I reinstalled all the patches which left me with a clean list of "installable patches". I did this once before and it worked for a while but things reverted to the "broken" state. The difference is that this time I first removed the IS_CACHE_ directories (actually I removed all but the "1st" one). Perhaps it will "stick" better after removing the extra IS_CACHE_ directories. We will see!
Last time this happened to me, I did try rpm --rebuilddb... No difference, it still showed the "already installed" patches. (The install on my laptop right now, however, has been behaving fine - FTP source for supplementary & the official SuSE install source via FTP, updated, everything, and it's still working fine. Now if we can only figure out the missing step that breaks it all :P