I have just performed some experiments and have indeed observed that the icon does not appear for every new email. It definitely appears sometimes but I have to experiment a bit more to find the pattern.