SpamCop no longer (as of Feb 25th, 2003) trusts relays which have not been submitted for relay testing by SpamCop. If you find your mailserver (or your ISP's mailserver) is not trusted ("recently discovered, untrusted as relay"), please avoid reporting it as the source of spam, but do submit it for testing (uncheck the box(es) labeled 'network where email originates' and leave checked ones labeled 'open-relay testing') After 48 hours if the system is not found to be an open relay or proxy (and it meets SpamCop's other criteria), sources of spam it identifies will be accepted by SpamCop.
One reason this problem can occur is because your internal mail server does not indicate the source IP address of the spam. Talk to your network administrator about fixing the problem.
The other, more complicated and more common cause of this problem is when the email bounces around the network too much, causing a chain error. This problem can also be solved by your system administrator. Don't let the email bounce around so much once it reaches your company's network. Specifically, change the setup so that all the mail servers in your company identify themselves in a consistent way.
The mail servers handling your email must identify themselves in a consistent way, and the DNS records associated with them must be correct. For instance, if a mail server identifies itself as "mail5.netcom.com", then the server must actually be delivering mail from an IP address (close to the one) given by that name.
Not confused yet? Then here's an even more technical explanation: For each "received" line, the receiving server must identify itself as being in the same Second Level Domain as the previous received line's sending server OR as being in the same Class-C (/24) network as the previous received line's sender. Whew. IP addresses used by mailservers must have reverse DNS (a mapping from an IP address to a hostname).
This chain-test is one of the primary ways of detecting spammer forgeries. Any relaxation of the rules involved would surely defeat the forgery detection and result in many more inaccurate complaints.
[Append to This Answer]