It is Immortel (or Immortel: Ad Vitam). Funny thing was, a friend of mine told me she had seen it. I'd never heard of it up to that point, but when she started with the pyramid floating above the city, I thought: 'Strange, sounds a bit like La foire aux Immortels, one of my favorite comic books by Bilal'. Then she went on about the blue-haired woman, and I thought, 'sounds like La Femme Piege', another of my favorite Bilal comic books.'
Later I looked up the movie and found out it was indeed based on those stories, and it was directed by the artist himself. It was a must-have.
Malk, your turn!