Ouch. Seems credit cards out of the US are nowhere near as good, common there to have no foreign transaction fees (apart from probably some margin on the exchange rate).
I use the Halifax Clarity card and I believe The Nationwide and the Post Office do a good card too.
I'd never use a Debit Card for foreign currency transactions though, they always seem to have fees involved.
Nationwide used to have commission-free cash withdrawals on their debit cards abroad, but I think it was abused by people who had second homes in other countries so withdrawn a year or two ago. I believe they still offer a commission-free credit card though.
Their "Select credit card" still offers EUR and USD purchases with no surcharge and no vig.