BTW, convince your corporate officers to allow you (or someone else preferably) to enforce the company's Data Access Policy. You do have one don't you?
If not, check out some of the usage policies at Universities and US Goverment sites (state and city policies suck) to get an idea as to what you might or might not want to include in yours.
Trust me, you do not want to play data nazi and have to enforce the policies yourself. Your role in the process should be to help draft the policy that your legal people (or mucky-mucks if you have none) will put forth as corporate policy. In addition, you should put the tools in place to allow for reporting of policy violations. You may have to generate the reports yourself, but ideally, the reports will be ran by the policy enforcer(s).
If your boss tries to stick you with the enforcement duty, just ask them who currently enforces the companies drug, attendance, etc. policies and they should see the light. Corporate policy enforcement is not the domain of an IT department. IT is there to provide technology to access and process any information that the business drivers require.
The reason I bring all of this up is that I can almost guarantee you that the addresses were culled from some form of mailing list that your (l)users are on. Whether that be some list served by a list server or some "You just HAVE to read this joke...it's funny!!" forwarding ring, your (l)users most likely were using company resources (email) for personal reasons thereby leading to your current problem.