They could do something similar to what Facebook does: as soon as they detect a new device using your account, send an email.
If the new device is not in the same country as your other devices, don't allow purchases until you've clicked on that link in your email.
And don't forget to ensure that you can't change your email unless you're doing it from an authorized device. Otherwise a malicious person could just change the email address where the notification emails are going to.
