Indeed. 500€ bill was known as "Bin Laden" because it was so hard to find one. It was estimated that 90% of the bills were held by drug dealers, money launderers and other criminals.
Edit: I suppose since it was an exchange outside of Europe, they probably wanna put them in circulation before they lose legal tender status.