I realized that this is happening months ago when I was not able to alter table structure in an instance of ArcMap after another instance was closed. When, for example, I remove or add some fields to a feature class in ArcMap, save and close the document and open ArcCatalog and attempt to delete that particular Feature Class I get the Delete Failed: Failed to delete selected object(s) error. This usually happens when an instance of ArcMap that contains layers which I am trying to delete is opened so the workaround is to fire up the Windows Task Manager and kill the ArcMap.exe processes that are for some reason still opened.
Anybody else having this issue?
Now running SP3 and the issue has not been solved.

EDIT: Just to add to the above information, I am running a very similar setup on a comparable machine and I do not have this issue there.