In Europe, for income tax deductible purchases, I need to provide invoices rather than a proof of payment. However, a business in California refuses to send me one, just saying they don't do that. Is that even legal?
We run into this all the time with our EU clients. As far as I can tell, the only requirements when it comes to invoicing have to do with sales tax, which is determined at the state level, and only in the case that items are taxable. It seems that the service provided to you is not taxable and so there is no obligation under Californian law to provide you with the invoice you need.
That said, it would be nice to provide this information to you as a courtesy. We don't provide the information typically required by EU tax authorities on our receipts either, but whenever one of our EU clients requests a more formal invoice we gladly send them one.