In Jaynes v. Commonwealth, No. 1054-05-4 (Va. Ct. App. Sep. 5, 2006), available at http://www.courts.state.va.us/opinions/opncavwp/1054054.pdf, a Virginia appeals court upheld a conviction under a state statute that criminalizes spamming. I haven't gone through the case in detail, but the First Amendment discussion may need some closer reading. The defendant said the statute prohibits anonymous e-mail speech. Part of the court's response was the statute prohibits only falsifying the source address, not speaking anonymously. If I correctly understand the standard that governs the format of e-mail on the Internet, RFC 822, section 4.1 requires that a properly-formed message contain the message's sender. See also sections 4.4.1 and 4.4.2.
If it's not possible to send a properly-formed anonymous e-mail message while conforming strictly to the standard, the statute may be open to constitutional challenge. The argument would be that you can't anonymously speak in e-mail without falsifying the sender information. If that's true, one solution would be to change RFC 822 to allow anonymous messages. Of course, every spam filter out there would probably immedately start dropping those messages, but that's probably OK because, as far as I know, there's no constitutional right to force people to listen to your free speech.