This started happening to me just after I got my new PC at work. I have PL/SQL Developer Version 7, Windows XP Pro and Microsoft Office 2003.
One time Excel froze up for whatever reason. When I killed Excel, a message box came up asking to submit an error report and recommended updating to Microsoft Office 2003 service pac2.
It's only been a week, but so far, I haven't had any problems recording macros after that. Maybe I'm just lucky, but it might be worth checking into. I think you can go to help/Microsoft online while in an office application and look for updates there.
One other weird thing is that I had the XP Style enabled and I noticed that it was off yesterday. I don't know if I just forgot that I turned it off or what. I don't know if that could do anything, but you might try toggling that off temporarily just to see. I set mine back on and it works, but I thought I would mention it.
Mike