Wait, don't scoff... look at the evidence.

Hagen enters the Family working for Vito, a mild-mannered and even-handed Capo Crimini who does not engage in unnecessary bloodshed. Then Mike takes over, and after the initial honeymoon period, develops a penchant for killing people at whim. If Mike can kill blood relatives, he would not bat an eyelid and killing adopted siblings.

Add into this the fact that Hagen screwed up while Michael was in Cuba - Kay got her abortion on his watch. Ruthless Michael presumably was not impressed.

This could explain why he tentatively ventures the questions "do you feel you have to kill everyone?" to Michael. Plus we know he was contemplating other job offers (see other thread).

Or maybe Micheal did have Hagen whacked between II and III. They never did see eye to eye, and after the Cuba/abortion thing ... who knows ...