Dungeon Keeper 3
Simon the Sorcerer 4. (It is being translated to English now, but I have no idea when it will finish)
Call of Cthulhu: Dark Corners of the Earth (Possibly, one of the most atmospheric FPS games ever. If you haven't caught on yet, it's based on the fiction of H.P. Lovecraft)
Vampire: The Masquerade: Bloodlines (It was a certain winner, however the company ran out of funds and it was released unfinished.)

Just out of curiosity have you played Age of Wonders? Same game type as HoMM but I consider it superior... And harder. Might be worth checking out otherwise. I have AoW: Shadow Magic. It's the third in the series and much easier than AoW 2 which was extremely challanging.
Karl

I don't know anything about this one. Why do you consider it superior? I think HOMM2 was basically perfect, and find it hard to picture what could be improved.

I'd love to see another Vampire: Bloodlines.
It's too bad Troika went under.
Though, Tim Cain does have a new MMO company he is with, working on some sort of unknown MMO.