Thanks for the input!
It looks like the problem has been resolved for now, but the cause is still unknown. I stopped the Virtual SMTP Server on my Exchange 2003 Server, and created a new one with the same configuration as the old one, however with a different name. After I started the service, I tested using telnet (locally). Now the RCPT message "xxx.xxx.xxx.xxx is blocked by Spamcop" was gone, and I was able to send and receive email from internal and external domains. So far so good, but like I said, I still don't know what caused the problem to begin with.
The BlueGateSoftware domain is my personal email email host, which I used to test the inbound messages. Each time I sent an email to my work domain it was rejected, with the NDR showing a different IP address, all of which were stated as being blocked by Spamcop, and which appeared on several RBL servers.
I have run anti-virus and malware scanners on the Exchange server repeatedly, and it appears to be clean - all the more puzzling. This weekend all machines on the network will get similar workouts, the thought being that maybe there is a machine on the network that passed a virus to the Exchange server and hijacked the SMTP service.