You could first check if they are a properly registered EUI-64. We’ve seen very simple AppEUIs that are clearly not registered to the manufacturer of the devices, but if yours look random then they’re probably fine (though likely not random, but that’s great).
Its details are not secret; the message is not encrypted and anyone in your (wide) area could receive it. So you could surely post those, and a screenshot of the device settings, if you want an extra pair of eyes to check. The AppKey is secret of course, so you’d better validate the MIC yourself.
I doubt that, but it’s actually easily tested with another (even different) device, if you got one? Note that @laurens uses a Tabs GPS, which seems to work fine, and likely also uses the built-in (non TTN-generated) AppEUI.
Any chance that at some point you deleted the application from TTN Console without first deleting its device? (Don’t do that.)
I assume there’s no (easy, non-destructive) way to disconnect the battery for a bit? (Like could one re-insert the plastic piece that needed removal before using it?)