Is honey really a supersaturated solution? Does heating to un-crystalize redissolve it or melt it?
Honey is indeed a complex mixture containing more than hundred compounds. 

As for Wikipedia and depending on the point of view it is


a supersatured liquid solution
a viscous supercooled liquid (in the sense that it can get so viscous as to appear solid, without affecting its status of being a supersatured solution, and undergoes glass transition).


https://en.wikipedia.org/wiki/Honey#Physical_and_chemical_properties

The facts that you describe in the question are less surprising if we consider that:


with respect to sugars crystallization, of which at least  there are two different ones, glucose and fructose, the rest of the non-sugar components must be considered to be impurities
impurities, even in traces, often hamper the crystallisation of a compound, even in simple mixture of a single compound and the above traces. This is common after organic synthesis, in which often a viscous "oil" is attained that might crystallize only upon prolonged storage or a careful removal of the disturbing trace compound(s)
finally and most important, the solubility of sugars in water is very high, and very sensitive to temperature. For instance, at room temperature glucose is already soluble in the reason of 90 g per 100 ml of water, that means a saturated solution already contains about fifty percent weight per weight of sugar


A table is here (I didn't cross check the values):

http://www.mpcfaculty.net/mark_bishop/supersaturated.htm

All this, viscosity included, makes the attainment of a supersatured solution particularly easy, as in the kitchen in the case of sucrose:

https://sciencing.com/make-supersaturated-solution-sugar-6199355.html

As such, heating crystallized honey does indeed dissolve the sugar, and a supersaturated solution is attained upon subsequent cooling.