First, I just want to say I do not have direct experience with what you are attempting to achieve, but I can make a suggestion which "theoretically" could work.
Intanjir's suggestions of using a different sugar with different dissolution rates is a good suggestion and may work. If not, maybe try adding a very small amount of a food-grade gum that has gelling capabilities, such as agar or kappa carrageenan. Probably agar would be better since it is typically much higher molecular weight and creates gels at much lower concentrations than carrageenan. Typically a firm agar gel can be made with under 0.5% in water but in a concentrated sucrose matrix you could get away with much lower amounts such as 0.2-0.3%. Hopefully this little amount added should not change the texture of the candy too much, but will create a network that 'should' slow dissolution.
My thinking is that kappa carrageenan is used to make those gel air fresheners, and as they slowly dehydrate they allow the entrapped essential oil aroma volatiles to escape over a steady time-release keeping your room smelling nice for a few weeks. Also, trying to re-dissolve an agar or carrageenan gel in room temperature water is very slow indeed.