Stover and Fire-C, thanks for backing me up guys.
Living in the Past, I think you're generally right that he did not race a lot in Europe (which made him a bit of a mystery man when he would just show up every year at the Olympics and win), but I believe that early on he was the two-time winner at the British national championships (AAA) in 1965 and 1966 in the 6 mile. I think he was disadvantaged in gaining further fame because as an North African he could not compete in the Commonwealth Games (unlike the Kenyans like Keino, as well as the New Zealaders, Australians, etc), which were big championships then, nor could he be in the European Championships.
In regard to beating Keino in 68, Gammoudi tells the story that he asked Keino if he wanted to train together before those Olympics but that Keino turned him down. Gammoudi was somewhat offended and said he then particularly enjoyed beating him in the 5K, where Keino was a big favorite at altitude (I almost hate to pass that story on since Keino seems like such a nice guy). In regard to Gammoudi's victory in the International Cross-Country championships, Ron Hill was in top shape then but wrote in his book that Gammoudi was just too strong.