Paypal (soporta euros) y 2checkout (solo USD) funcionan y muy bien con OScommerce.
Y son pues, bastante baratos.
Otro que no es barato pero soporta muchas monedas y paises es :
www.worldpay.com que es muy usado.
Ya pues hay otros más aunque en su mayoría son para merchant accounts solamente ... fijate :
www.paysystems.com www.echo-inc.com www.onlinedatacorp.com www.charge.com www.merchantservice.com www.merchantbankcard.com www.safesolutions.com
Espero te sea util la info.
Saludos.