Charter One Bank has pre-paid MasterCards available online. Lots of people do that, I know, but Charter One does not charge a service fee, and they don't even charge you for shipping & handling. You choose an amount from $20 to $500, select a message to be embossed into the card, and enter the recipient's name and address. The payment is funky though—your only option is to take the money off an existing credit card, which presumably will be charged as a cash advance. Maybe using a debit card will work?