I missed your comment about not having a microwave, kitchengoddess. I would imagine defrosting muffins in a toaster oven would dry them out. I also agree that freezing muffins can affect the flavor if frozen too long. I always store freshly made French bread on the counter top in a plastic food storage bag, squeezing as much of the air out as possible, then tie it with a twisty. This likely doesn't protect the bread from mold, but it does keep it soft.
Good luck! Let us know if you found a method that works for you.