The only thing that kept me going on this was excellent communication with both my new manager and HR. They guided me through the process and were very honest about where we stood and how I should answer ambiguous questions in the application. I was certain I would pass the background check but nonetheless it felt unnerving to let those other offers expire for something that was not really a sure thing.
Also some of the background checks can cost quite a bit more than $500. The preliminary ones are fast but the thorough federal one I'm undergoing now takes around 6 months.
I passed a similar one a few years ago which cost the employer more than 30k and took more than a year to compete.