Hi Ray,
We are still using Linked clones and not instant clones. Would we be facing the exact same issue as the linked clone machines are not being deleted after use, we just do a refresh after using it.
I pretty much have no clue whatsoever about Horizon, so I just checked with, umm, sort-of-HorizonDev 
. They indicated that the shutdown process for Linked Clones would be similar, so I'd love it if you could try the workaround.
As for the different delays you're seeing: I'm not quite sure, to be honest. A single machine shutting down can cause the delay for multiple clients, and leases also expire on the server side after a little while, so the exact symptoms are rather sensitive to timing.