You can try Authorized.net. Are you looking to make recurring payments? There are many out there but i find many do not have fraud protection so be sure you have protection.
I have been checking into them, do they accept checks for recurring payments as well? Can you give me more info on how they do not have fraud protection?