We use Braintree and they're great. We're not doing $250k/mo yet but had no problems getting signed up with them back in May.
We also helped a partner company get setup with BT recently. They're doing < $50K a month IIRC.
Have not run into most of the problems mentioned in the OP.
Within the last year, I've been in the position of doing <$1k/month on a credit card processor, and it was actually a delightful experience. The company I originally worked with was bought/renamed or something and I haven't had to deal with them in quite a few months, but I can probably dig up a contact. Email me if you like.