I don't verify addresses, but I do include unsubscribe instructions. Is that enough?
You must verify addresses added to your mailing list. It is not acceptable to add recipients to your mailing list on the assumption that they'll unsubscribe if they were added against their will.
If someone is subscribed to your list against his will, by accident, or by another malicious person, he probably will not consider the mail to be legitimate. He won't know whether you're a spammer or not, and probably will not use the unsubscribe instructions you provide: people have been told by reputable sources such as Consumer Reports magazine that they should never try to follow the "removal" instructions in an unsolicited message.
So the recipient will likely ignore the first few messages you send, then report you as a "persistent spammer" if the messages keep coming — and he'll be right, in the sense that he didn't agree to get anything from you and you keep sending him unsolicited bulk mail.
Compare this to what happens when you use a proper verification system. If you verify the address and the recipient ignores it, the recipient will receive only one message from you and probably won't complain. Even if he does complain, no anti-spam organization or ISP treats reasonable subscription verification messages as "spam".