I have an Imagio on my Alltel plan, and my MMS works just fine with the Verizon server settings. In fact, if I put in the Alltel settings, it does not work.
Did you try it with the verizon server, or did you just assume it wouldn't work? I would try the Verizon server again.
Name: Verizon Wireless
Gateway: Blank
Port: 80
Server:
http://mms.vtext.com/servlets/mms