It would take a minute or less for an envelope to thaw, and several more minutes to come to ambient temperature. Coming to ambient temperature would be the important thing.
Some say that refreezing is not good for pollen. I have never seen any data or even heard any anecdotes that back up the claim. On the other hand, I have heard anecdotes of people using refrozen pollen with success. However, I would keep it to a minimum, as I am sure there is a limit that could differ depending on the genetics of the pollen.
