Should Eldritch Tokens only be used as tokens for the original reason they were placed?
Typically, you use a straight forward reading of the rules/instructions in EH. In this case they indicate that the tokens are interchangable.
The mystery you refer to also clearly states that any Eldritch tokens remaining on the board when the mystery is solved should stay on the board. This rather strongly indicates that (in this case at least) it is intended that all Eldritch tokens can be used to resolve the mystery and that you must abide by the travel restrictions on all the (new) tokens that the Cthulhu AO has.
Also, I'm sure that if the intent were other, they would have included alternative tokens. This also hasn't been mentioned in any errata document from the publisher. So, I'd go with the instructions as written.
Further, this correspondence was received from FFG in answer to the question, which seals the ruling:

An Eldritch token is just an Eldritch token. If placed on the board or a card, it has no inherent effect. They act or affect the game as instructed by any effects that reference them. Players are not expected to remember where any given Eldritch token came from.
An Eldritch token placed by a Mystery is exactly the same as an Eldritch token placed by Cthulhu’s reckoning effect. In such a case, Eldritch tokens on the board represent odd happenings or areas under the influence of Cthulhu.