My problem was fixed as I said, but temporarily after all.
The initial problem to be honest(some months ago) was that there were 3 particular updates, that although they seemed to download and get installed correctly, when I'd run windows update again(after a PC restart), they would still be there, like they were never installed in the first place.
Then came this problem of 'could not search for updates'.
Not sure if they are connected.
And to answer your questions:
*Last successfully installed update: Security Update for Windows 7 (KB2676562)
Security Update for Windows 7 (KB2633171)
Update for Windows 7 (KB2679255)
but not sure if they can classify as 'successful', because as I said I have installed them several times :/
*My antivirus is avast!
*No recent malware episodes -but since this is isn't a recent problem, it's not that helpful i guess