To clarify, it's not that Travelex is located in or operates in Europe, it's that they hold data of EU residents. If they operated in Zimbabwe yet held data on EU residents, they would still be bound by GDPR.
In a hypothetical situation of a non EU company significantly breaching GDPR this could be resolved by e.g. seizing all funds belonging to the company in EU banks or in extremes by finding the company's board in contempt of court and then arresting and imprisoning them if they ever travel to a country with a extradition agreement.
But your question is interesting. Imagine an onion service, theoretically perfectly shielded, that took Personal Data from it users and then sold it. Or even a normal Internet service, based in North Korea. GDPR would be unenforceable.
Ultimately we depend on the norms of international agreements, the desire and need to interoperate with global banking systems, etc.
The GDPR text basically says "we'll ask other countries nicely and negotiate with them".
I'll be interested to see how the first real case goes against even a US-based entity that doesn't operate in the EU, much less one based in a country like North Korea.
..they'll ask all the EU ISPs in each of 28 member states to block company X - nicely.
() "EU citizens" meaning potential customers of company X - the "enticement" for company X to pay the EU the fine.
All kinds of companies, from all over the world (eu or not) flooding the GDPR headquarters in Brussels with "pre-emptory warnings". The purpose of course being to let them know how ridiculous (and possibly/probably arbitrary) their regulatory framework
And is anyone else annoyed that since GDPR started, every single website that even so much as stores your username now has a "this website uses cookies" thing you have to click on to get rid of it? And if you turn off cookies, you see this damn intrusive thing every single time. How is this making the web "safer"?! Can "we" (whatever that means) petition them to enact a standard where people can set a preference in their web browsers that says "I don't care unless it's financial/medical/physical-address data" It's a $#%$5# pain in the collective derriere.
I wouldn't be surprised if some websites are doing it as a matter of course, "just in case" - like the "this product contains things that are known to cause cancer cause cancer to the state of California" - applied to everything - in a catalog that sells drill bits (okay, I suppose the couple of nano-grams of drill-bit-dust coming off it). Just to be safe (pun unintended).
I am indeed very annoyed that so many companies are throwing an online tantrum over the very reasonable requirements of GDPR. Most of those cookie banners aren't even GDPR-compliant because they don't let you opt-out of tracking and don't actually tell you what data they are tracking or who they are giving it to.
Just tell people what you are actually fucking doing with their data and let them opt-out of having their data collected. It's not that fucking hard.