Trademarks mean nothing. A bigger company can always come along and bully you till you give it up. Just like what happened to Allen Pan and his Mythbusters trademark.
If you had 2 people documented as being in the EU who had purchased software licenses for 'Deepkit' for $10 is that enough? If not, why? Why is being big[1] justification for outright stealing a trademark from someone little? It's gross, is what it is. I'd rather eliminate the whole trademark construct than have it just automatically side with the largest party in any contested case.
[1] also, they may only be 'big' in terms of bank account balance, since they're some startup -- they may not have any EU customers yet themselves. Did they prove they did?