>> On my server, there is no run-parts in /usr/bin.
>> Indeed there are no files called r* in this
>> direcory at all!
Well, you've found the origin of the errors. This is the point where professionals call "restore from backup", that would be the best solution. If you don't have a backup, perhaps you could get one from someone else. Just restore this directory and check for other errors.
If you're missing files in this directory, you might be missing more, check /var/log/messages for more errors. A backup to desktop, re-install and restore should fix everything. (I'm not 100% sure that you won't loose something, but you should be able to find more in these forums about re-installing) A re-install without backup will erase everything !
There's still the question how these files became missing. You need root access to erase run-parts, something strange has happend here.