tearing down exhasted mines never regain building licence

[Boudicaa]

Have the same problem - dont get licences back - I dont have many and pays a lot of attention to the number

[Fexno]

You already got them back when you mine collapsed (ran out of ore)

Also see Iolanthe's earlier post:

Actually, that is normal. The License comes back when the Mine empties, not when the ruined shell is demolished. If you're offline when this happens it can be very easy to overlook.

If you demolish a Mine when it still has a few Ore left you should see the License reappear and get back some of the resources used to build the Mine. That said, "refresh" really is your best friend in this game, it will cure many and many a small bug.

Hope that helps a bit.