I heard somewhere on this list that if a 404 page is not of a certain size, IE will not display it. Could this be your problem?