People should have every right to unsubscribe themselves from that, and thus should have some sort of feedback loop attached to the email being sent (to the detriment of your bottom line I fully understand and sympathize with).
If this was indeed a marketing email, then I don't think it matters if it comes from a "legitimate, paid service" - the receiver still should be able to choose if they want to receive sales related emails wouldn't you agree?