In the instance under discussion, isn't there a difference between device and hard drive for the purpose of Apple's counting? If the replaced hard drive is not used anywhere else, then the count has not changed. Otherwise, more users would be burning up their allocation just from restoring via clones or TM backups.
I don't know Apple's process here, but I would imagine that for counting they would look at some kind of hardware ID, and if that does not change, then the count does not change.
There's no fixed standard for how to do this, but most vendors take the same approach that has been refined over the ages with various software experiments:
Before activating, the software will at first launch generate some large random seed. It then record this information as well as any license code and some unique information from the computer's hardware. The serial number of the computer is commonly used, as is the MAC address on the default ethernet or wifi port. (often both) Microsoft Windows records a great deal of additional information including your graphics card and hard drive serial numbers. This information is combined together ("hashed") to create a globally-unique seed. When activating, this seed, along with all of the gathered information and credentials, are sent to the activation server as details in an unsigned certificate. (CSR file - a Certificate Signing Request)
After validating your credentials and license availability, the activation server signs this certificate and sends it back to your computer. The software saves this signed certificate. (commonly referred to as the "license file") Anytime it launches, it will verify the signature before it will run. If any information on your computer changes compared to what's in the certificate, the software may refuse to run. (windows will let you change a few minor components, or one major component, any more than that will fail the comparison) Most software doesn't record as much and will refuse to launch if
any information differs from what's in the certificate.
You can't "hack" (edit) the certificate and change information in it to match your current configuration, because that will invalidate the signature. If your hardware changes, you have to submit a new activation request and get a new certificate that matches your hardware and is properly signed by the activation server. As with any asymmetrical key system, the software on your computer is easily able to verify a signature is valid (using its copy of the public key) without having the ability to create a new, valid signature, which requires the private key stored only on the activation server.
On the mac, the software doesn't even have to manage this certificate or its public key itself. It'll just hand it off to the user's keychain using the built-in certificate management system in OS X.
This prevents you from say, copying software and the license file (certificate) to another computer and running the software there. Or even moving the entire hard drive to another computer. It may also cause your software to deactivate if you change your hard drive (even if you DO klone the data over) or change the logic board in your computer, or the wifi card gets replaced. (when Apple replaces a logic board under warranty, they klone the serial number from your old board, BUT they DO NOT klone the MAC address on your ethernet port!)
Although I don't know for certain, it's reasonable to assume the AppStore computer-activation is done in the same way. I know every time I've had to restore from a time machine backup I've had to re-activate my computer for the AppStore. I assume this is because the GUID (random serial number created when you format a volume, and time machine DOES NOT klone the GUID of the volume when restoring) is part of their certificate information, seeing as my hardware and software did not change. But because Apple allows you to have up to five computers (and unlimited iOS devices - that actually have SOME limitations they don't publicly disclose) I only ran into a problem once and needed to use a once-a-year full reset of my count. (but then I had to reactivate my other computer and iPhone because their certificates got revoked when I reset)
So I urge you to sign out of any licensed services before making significant hardware changes or discarding your gear. Otherwise someone else may be able to use your services, or it may inconvenience you by making one of your granted activations inaccessible.