Rethinking taking @americanexpress in the day job

Long backstory which boils down to this: Every time a customer tries to pay with AMEX, we have to deal with a broken/borked verification system. None of our other credit card companies have issues, just AMEX.
This time, they called up and questioned we were legitimate.
Ok.
They really did.
I am going to start recording my calls with them, you know, for quality, and entertainment, purposes.
After 5 minutes of dealing with the rep who called us, I asked for her manager. Spoke to them for a few minutes, and while trying to restrain my anger at their broken processes causing us grief, wasted time and effort, I asked them, point blank, whether or not they did anything to verify that we are whom we say we are, independent of us, like … I dunno … googling our name and address? Contacting the town where we allege we are located? etc. ?
I must have hit a nerve.
A few minutes after this call, this referrer was in our web logs.

http://www.google.com/search?q=SCALABLE+INFORMATICS+9282+GENERAL+DR&hl=en&tab=lw&safe=images

(truncated of course).
OMFG.
You … cant … make … this … stuff … up.
No one else has a problem paying us. They do.
I see a very simple solution to this. Really simple. I mean, it solves all my problems.
And in the mean time, if they use any more of my team’s time, I am going to send them a bill for the time/effort/resources that they wasted.
So since @americanexpress questioned whether or not were are legitimate (yes we are), let me turn the question around. Are they? Could I in good conscious allow my customers to use what might not be a legitimate business? Maybe I should demand documentation from them before I will take their cards. After all, they represent an increased risk to us that we will not be legitimately paid, by failing their financial middlemen responsibilities.
Lets see what happens, I suspect in this case, we will have to call our customer up, have them wire the payment, cancel the AMEX transaction.
This is a case of #fail . Bad process initiated #fail . An unforced #fail . It is not pleasant to experience. That someone thought that this was a legitimate way to conduct their business?
/sigh