Another option for a service would be authorize.net, but I've never used any of them, so I can't give details beyond throwing another name out. This is something I'm about to do for the first time, too, and probably would have asked within the next day or two if you hadn't beaten me to it...
Comment on Re: Using PayPal, Google Checout, Amazon FPS to sell products, driven by perl
It would appear that authorize.net's signup form is broken at the moment, so I can't sign up to get more information about how to use their Merchant Services.