Hmmm... I wonder if you sent your message as an MMS, if that would work around the Unicode issue on Verizon? MMS content can include text; in fact, there are some phones I've seen where you can force it to send everything as MMS.
I don't know of a way to do that on the iPhone for every text, but I believe that the Messages app in iOS will encode the entire message as an MMS *if* you send to multiple recipients. So you could try to send a text message with Emoji included in it to multiple people, with one of the recipients being an AT&T iPhone, and see if the AT&T iPhone gets non-garbled Emoji when you do this.
Another thing you could try would be to send a text message to an AT&T iPhone from Verizon via AT&T's e-mail-to-SMS gateway. If you send an e-mail (from the Mail app, say) to
2125551212@txt.att.net (where 2125551212 is the 10-digit mobile number of the AT&T iPhone customer), the contents of the e-mail will be sent to their phone as an SMS, but if you use @mms.att.net instead, it will send it as an MMS. Try to send them an e-mail full of Emoji using the @mms.att.net address and see if they get it as an MMS, and see if the Emoji is readable inside the MMS once they receive it.
If that works, and if Verizon allows you to send e-mails vis SMS (if you can send a "text" to, say,
2125551212@mms.att.net), then you can send Emoji "texts" from the Messages app that way. It's cumbersome, sure, but it would work (assuming Verizon's SMS-to-email gateway doesn't have more "magic" that prevents UTF8 characters from passing through).
Long-term, either Verizon needs to fix their inter-mobile-provider SMS gateway to transparently pass along double-byte characters, or Apple needs to add an option to Messages that allows you to specify that you'd like text messages to be send as MMS, or someone needs to develop a Cydia extension that does the same.
-- Nathan