Yes, I'm aware of that, I think that's how I unlocked the other altars

The only thing I can think of is that, on a previous occasion (which I've inconveniently forgotten) I was in Taurog's subdungeon and did something to piss him off, and now I'll never have a chance to worship him. Is that the way the game works? So I need to create a new kingdom if I want to worship him?
I've completed the following dungeons in the western hemisphere : spike trouble, venture cave, grimm's groto, the chokebox, ick swamp, southern swamp, hobbler's hold and western jungle - still no sign of Taurog.