Are you certain that you are seeing relays? Another possibility is NDR spam of sorts. Is your server setup to send non-delivery reports for invalid or non-existant email addresses on your domain? If so, directory harvesting type attacks will create huge amounts of outgoing traffic to email addresses that usually don't exist (forged headers) which are, ironically, in response to receiving a message sent to an address at your domain that doesn't exist.
I would guess that something similar is what you are actually seeing, and not an open relay. If you are certain it is relaying, what version of Exchange are you using?