With that in mind, I think the reason is that people buying Euros are planning to travel to Europe and spend their banknotes. And they probably are buying a couple hundred Euros, not thousands and thousands, just a bit of cash for peace of mind. They wouldn't want to be stuck with such large denominations, because it would be hard to spend them. If anyone is planning to move to Europe or invest in a European company or anything like that, they would use wire transfers, not banknotes. Banknotes are generally just for small amounts used by travellers. Thus, the demand for large banknotes is lower, which causes their price to be lower.
I wouldn't be surprised if forex shops have to send the majority of large EUR banknotes physically to Europe to deposit them into a bank account. That would explain the extra cost.
However, I did notice that some countries still have large denomination bills - Singapore (1000, until recently had $10,000 bills), Switzerland (1000), Brunei (10,000).