I just read Naming Workstations on a Windows Network and had to smile a bit. Something as simple as your workstation naming scheme can be a very complex process that is different for every single network from 10 users to 10,000. It just goes to show how varied our field is and how many different ways and opinions there can be.
My current job names workstations by OS and username. I dislike this scheme. At my old job early on I inherited and used a similar method where I named the workstations after the usernames. We had a smaller company of only about 60 users, and by the time we grew up to 150, we had had a security audit which pointed out that machines named in such a way leaked too much information (Low priority, I believe). Wanted to target the CFO? Find his name, enumerate the network, and you likely also have a username that has rights on that machine.
I switched us over to naming machines “wkst###” and maintained both an Excel spreadsheet mapping workstation name to the user assigned that computer (we checked out equipment to all employees) and also inventory management software which let me regularly map MAC, IP, usernames, and workstation names together. This way if “WKST125” was doing something naughty, I could very quickly isolate it, take control, and/or check on the user. Having administrative access on switches and remote control capabilities takes away a lot of the need for user-named or even departmental-named workstations when you have an inventory of MACs and domain admin rights! I never did reuse names either, and I had a strict personal policy that no machine was re-issued without first wiping and re-imaging it (sadly, some colleagues did not adhere to such policy later on), thus a perfect opportunity to rename it. I might leave orphaned entries and artifacts this way, but I would rather have orphaned data than data that might actively be lying to me if it wasn’t kept up to date.