Currently, the average coal fired plant produces electricity at 33% efficiency: https://www.energy.gov/fecm/transformative-power-systems. That's average, so there are probably plants out there producing at 30%. If we assume another 5% loss for transmission, this takes us down to 25% efficiency as delivered to the consumer.
If a heat pump is 3x the efficiency of resistance electric heat, but you are burning 4x the coal to generate the electricity, are you still certain that a 95% natural gas furnace is never the better choice for efficiency? I'm not. I think the heat pump is probably more efficient in many cases, but I wouldn't eliminate the possibility that there are cases where the natural gas wins.