We had a very good experience with the folks at Security Metrics in Utah. Very reasonable people. And. We had some compensating controls and non standard things to be done. They were very much willing to work with us instead of against us.
I had a mixed experience with them - their automated scanner can be painful with misdetection, but their support usually makes up for it, even if they're slow to respond. I've not used them for anything other than the quarterly scans.
Hi Tom, very biased here, but I interned at MWR InfoSecurity and the team there seemed to be consistently very high quality (like finding 0-days in Chrome, Windows Kernel, etc) - would definitely recommend looking at them.