We're a US-based company that has been asked for an EU VAT id - what to do?

Surely we aren't the only ones that have faced this. A new customer of ours (based in the UK) is trying to set us up as a vendor and sent us a form to fill out. The assumptions on the form are that we are an EU company. (We've responded and asked for clarification and alternate process)

Should I try to figure out how to get a VAT ID (Not something I want to do) or are there other suggestions?

This was unexpected. We were dealing with people in the US (it's a pretty large global company) and in the UK and I was not expecting this kind of issue yet.

How have others dealt with this?

To deduct whatever they purchase from you, the UK company only needs your invoice. In the EU, a EU-registered company is usually required to place their VAT ID on their invoices if they sell to a company that is also in the EU - also, they are required to add the VAT ID of the buyer to said invoice (if the buyer is not in their own country, but in the EU).

Since you are not in the EU, none of this applies to you. The UK company does not need any IDs from you and they are asking you for one in error. You certainly do not have to get a EU VAT number - you can't get one anyway if you're not incorporated in the EU.

Note: I'm not a lawyer nor an accountant. We are in the EU and we're doing business with US companies all the time. If you want water-proof confirmation of this, you should consult a lawyer or accountant.

Both U.S. and U.K. companies technically owe sales tax (the U.S. equivalent of VAT) when they have a physical presence in a state. For example, if you set up shop in California and you sell to customers in California, you are required to pay sales tax. Amazon has tried to get around this rule by taking out any physical presence in states in which they do not want to pay sales tax.
The same is true abroad -- whenever you have a physical presence somewhere, you owe sales tax or VAT. The UK company is being highly precautious since you may not even have any connection to the UK.

Technically what he is doing is legal though most companies try to avoid it as long as possible. You are simply dealing with a customer who is extra precautious and wants to comply with the law of the UK.

From what I understand, you should charge VAT if you are selling non-tangible goods to a consumer in an EU country. If your sales are B2B then the receiving business has the responsibility to self assess the VAT due.