Back then I’ve been using Plimus, but they degraded over time so I had to move out of them. At this moment, I have good experience with Avangate (now called 2Checkout) so if you’re looking for a payment processor, I can advice them.
I also analyzed payment problems with FastSpring, and it seems that majority of failed payments (when some of my long term customers suddenly were unable to pay) happen for customers from Colombia, Brazil, Chile and other Spanish-speaking countries. If they are not your target market, probably FastSpring will be good too.