Robert has answered the question quite well, but I will elaborate:
Taking off into a strong headwind is not difficult as such, but as Robert (and John as well, in less subtle way :) pointed out, taxiing in strong wind, however steady it might be, is a real pain it the seat of the pants. Since the question is about taking off, lets assume the plane would (magically) get to the end of the runway safely. The takeoff itself would then be something along the lines of what can be seen for example in this video:
Youtube: STOL Competition - World Record Shortest Landing 9 Feet 5 Inches
(Yes the title says "landing", but there are plenty of takeoffs to be seen)
Nothing special really, except you are airborne in a blink of an eye. What might be troublesome to an inexperienced pilot, is that the visual cues are weird, so airspeed would have to be monitored with great care as referencing the surroundings would be useless. Also: great wind speed at ground level guarantees there will be turbulence, so maintaining appropriate airspeed is critical, and lifting off the plane should be "decisive" to avoid being pushed back on the ground by shifts in wind. The question states a wind speed just under clean configuration stall speed, so you would not use flaps, since as soon as you would lower them, you would lift off.
As for the part of "Is this something that happens often?": No. Outside the realm of STOL contests, during normal operations: this does not happen. Regulations and POH limitations set aside, you just could not get on the runway in one piece.
P.S. It is worth noting that majority of STOL contest planes are taildraggers, so this gear configuration certainly is not a disadvantage when taking off or langing at windspeeds closing stall speed.