Here's a weird one i tried to find for so many years:
I believe it is called "Geotran" or"Geotrun" (or maybe even "Geo-run"), and it was for MS DOS. (pretty sure about that)
The goal of the game is to solve an enigma, or an object to find, you play against other players (CPU or local multiplayer), and to do so you need to travel the world to find hints using planes. The player who solves the enigma (or find the object) first wins the game.
You could choose the CPU characters to face before starting the game, and i remember one of them was called Natasha and she was russian.
Each CPU character also has a little jingle that either introduces the character or it plays when one of them win the game, and i remember her jingle, i can even sing it, i believe it's a popular song but i can't name that either.
The gameplay is basically the world map (with a bunch of UI stuffs around), you have to travel the world visiting cities to find hints and you need to plan in advance your travels checking things like the weather and other events in order to save time.