Stolen iPhone 13 Pro Max

FWIW, you fell for an all too common scam; these scams CAN be very sophisticated and appear VERY convincing.

Unfortunately, your prepaid carrier - who has no real allegiance to you - gave you bad info.

Apple can not / does not blacklist devices by IMEI.

That is solely a function performed by carriers; and unfortunately only applies regionally. There is no “global” blacklist.

(e.g. a phone blacklisted by a European Carrier might still be usable on the network of an Asia/Pacific Carrier)

Chalk this one up to a learning experience and stay vigilant.

Recognize and avoid phishing messages, phony support calls, and other scams - Apple Support

Use the built-in security and privacy protections of iPhone – Apple Support (AU)

Well, you certainly have a mess on your hands.

The only way the device could be removed from your account was if the thief knew your device Passcode and possibly your AppleID credentials as well

If it’s not on your account … it CAN be used … at least until your carrier blacklists it (not all carriers do this)

You should also consider your AppleID compromised and take the appropriate actions.

If your iPhone, iPad or iPod touch is lost or stolen – Apple Support (AU)

If you think your Apple ID has been compromised - Apple Support

For future reference:

Your iPhone is incredibly well-secured by it’s passcode. If a phone is lost or stolen there is ZERO need to panic. Most government’s can’t even crack into it.

Remain CALM … a stressed human is the iPhone’s greatest vulnerability. (which is why this phishing scam evolved)

The passcode … combined with possession of the physical device counts as “Two Factors”. (Something you “know” + something you “have”)

Once so-armed, the crooks can reset your AppleID password w/o actually knowing it. 😕.

So the lesson learned is NEVER EVER enter an Apple device passcode into ANYTHING other than an Apple device which you own and physically control.

Keep your passcode VERY secure; it really IS the “key to your Apple kingdom”

In this regard, suggest creating a long numeric custom password. A 10+ digit numeric passcode is easy to enter but tough to surreptitiously observe and record.

Re: … Do you think it’s still worth it to try another store and ask them to block even it’s just for Europe? …”

If I were on vacation in Europe w/ a baby …

… I’d leave this one in the rear-view mirror.

You’ve got much more positive things on which to focus.