They both mean the same thing between something. Ανάμεσα is informal, while μεταξύ is more formal Μεταξύ can also be used to say something like "We will meet between 1 and 2 o'clock"->"Θα συναντηθούμε ανάμεσα στη 1 και στις 2" which is very formal and rather uncommon, there are also some expressions like "Αυτό να μείνει μεταξύ μας" which means "this better stay between us" or "εν τω μεταξύ" which means "by the way", that you have to use μεταξύ over ανάμεσα
How different is this to the familiar English saying "Between ourselves", which was marked as wrong when I tried it?
In my opinion, as a native speaker, between ourselves is a translation for μεταξύ μας, not ανάμεσά μας. There is a difference in meaning, at least in this case, in that context. The first one would be used for, let's say, a secret, and the second one is a slightly more generic.
There might be aliens among us - Μπορεί να υπάρχουν εξωγήινοι ανάμεσά μας.
They live among us! - Ζουν ανάμεσά μας!
It's a secret, so keep it between us. - Είναι μυστικό, οπότε κράτα το μεταξύ μας.
In the secret-keeping context, I wouldn't think of using among (ανάμεσα), and in the more generic context, I wouldn't think of using between (μεταξύ).