Also, to pull back from my rant a little -- when dealing with a customer service department that can only read from a script, this should always throw up a red flag. The documentation you say you have available is about 6x what most other sellers on eBay/eBid/eTc have or offer; since each piece you sent them is verifiable then it shouldn't be a problem for them to consider you verified for all intents and purposes.
How will eBid handle multi-brand outfits (like mine -- I have one set of employees running multiple selling outfits under two roofs, with different seller accounts for each.) By eBids terms and your experience, I couldn't do that. How will they handle sole prop businesses, which probably don't have utilities in their DBA? How will they handle sellers who operate out of flea markets, and therefore have no business utilities of which to speak? Trying to put a uniform rule on that, and then simply summarily rejecting attempts to clarify and verify your identity, just smacks of unprofessionalism on eBid's part.
Also, YSE shows
"Failure is not when you fall down. Failure is when you don't get back up."