I'll ask my business partner to see what they might be but with that many transactions, have you looked at Verisign or LinkPoint. Verisign will give you 1,000 free transactions and LinkPoint won't charge you any thing for transactions.
Also, are you happy with your current provider? If so, I would not recommend changing, talk to them to see what they can do for you. Usually changing just causes more problems
LinkPoint is an electronic payment gateway - just like Verisign's payflow services and authorizenet.com. It offers the virtual terminal is is mainly sold thru Cardservice. It is re-branded and sold thru with Chase and a few othr larger MAPs as well.