Yes they do get re-allocated. Originally, an australian domestic airline called TAA (Trans Australian Airways) was allocated TN. This airline then changed its name to Australian Airlines and continued using TN until it was bought from the Australian government by Qantas. Qantas retained the registered company name of Australian Airlines but not the TN flight designator which has since been allocted to another airline (can't remember who).

Now that Qantas has re-launched the Australian Airlines name as a low-cost international service operator, it cannot use the TN flight designator or the original Australia Airlines.

With almost as many mergers and closures as new airlines, there is plenty of scope for re-use. But it can confuse some on-line reservation systems.