The difference has to do with their meaning
"at" - refers to a physical location
"in" - while it does refer to physical location in many cases, but with your usage, it is referring to a state of being
If you notice my bold and italicized words, that is an example of a state of being
A clear-cut example is:
He was in a coma
where coma is a state of being
A clear-cut example for your usage is:
They stayed in contact
or
They stayed in contact with each other
where "in contact with each other" is the state of being
I would try to define state of being better to you, but in English there is no way to define the word being, therefore state of being can not be defined. The only way to define it is to provide synonyms or explain it to you via examples.
A synonym to state of being would be state of existence or state of existing
Just Noticed Something:
In the phrase:
...their attempts at contact with their European counterparts.
technically "contact" is not a real physical location, but rather it refers to a symbolic location on the timeline, so the rule here about location still applies