I've made several attempts, but they're asking for things like phone bills in the name of my company, but since we don't have physical offices, I'm unable to provide that. How did you proceed?
You should be able to get away with a bank statement listing the name of the LLC, any local DBA (fictitious name registration) and whatever your secretary of state gives LLCs to prove they're registered.
I'm sure they won't like it because it means a human has to get involved (probably a couple humans) for a few minutes which means their RA isn't the cash cow someone promised management it was going to be. (Having worked for three CAs, I have never known one to be a profitable profit center.)