I have the sheeva plug running PPPD in a persistent mode top maintain the 3g connection and a script that pings google.com every 2 minutes to keep verizon from dropping the connection.
I have the wonderful linux iptables doing some work as a gateway from the ethernet port to the 3g modem. Works perfectly, 100% reliable.
To save money I plan to get rid of the 3g plan and add an android phone to my mother's family plan and since she's a teacher in MA she gets a 15% discount. $9.99 to add a phone, $30.000 for data... $40 x .85 = $35/month. I'll likely root the phone and do some networking magic to turn it into a decent internet connection with enough IPs to go around. I may even just attach it to the SheevaPlug and have the plug dial it as a modem...