I played this game in Germany. It was called Asterix and Obelix Die Große Reise (The Big Journey). I enjoyed playing it and I'm trying to find it in English. So far I've only found the CD-i version, but since I don't have a CD-i player, it's not much help.
I usually get my old games from ebay or marktplaats.nl, and with both the motto seems to be: "If they don't have it today, maybe next week." More than once I couldn't find games I really wanted to have, but checking back regularly usually resolved the problem. Online auction places are usually the best way to get old games, in my experience at least.