Hey tubi417-
The technique they used in the experiment involved raising antibodies to whatever bits of hemoglobin were left. Creation of antibodies in this way doesn't require that any functional protein or protein pieces remain, since very small fragments will work. (I'm not even sure they specifically stated intact heme was there, though they showed a diagram of it, I think...)
I'm not sure how long protein fragments would last - apparently this was a rare finding, so it might be a matter of just the right fossilization conditions and a lot of luck...
™ Version 4.2