To answer your questions…
Guide 25 or national equivalent: If you're in the states, an equivalent would be ANSI Z 540. But be cautious. I think most accreditation bodies accredit to the ISO Guide or standard (17025).
If they aren't accredited: Find one that is. Most registrars are writing the use of a non-accredited lab as a major.
If it's the only lab that can perform the test: This is a tough one. I think I'd be prepared to provide documentation to support my search for an accredited lab. You might be able to fight it.
Is the closest lab/best turnaround lab: Too bad. If the lab you're using is not accredited and others are, I think you're stuck.
Is the most cost effective choice: See above.
Can you perform an audit: I don't think so, unless you've been certified as an "OEM customer approved second party".
Is there a checklist: Yes there is…see the A2LA website. It's readily available, but based on the answer for the last concern, I think its academic.
Requesting a waiver: This is probably your best bet. Customer requirements always override the standard. Make sure it's written evidence and clearly states that you don't have to comply to the specific sections in the standard.
Does this include everything: I'd say yes, unless you have an explicit wavier from the customer.
These are my opinions based on what I'm hearing in the industry. Good luck to you.