I know I need to remove my current license on the soon to be recycled 32-bit PC before I can use the same license on a new 64-bit PC.

Does the older computer need to be connected to the internet for the deactivation to be recognized?

Does having used an upgrade from V5 to V6 to V7 license matter?  I still have the license keys for V6 and V7.

I believe the old PC does need to be online to deactivate the license, since Macrium needs to know that the deactivation occurred and therefore that the next activation attempt with that same key should be allowed.  If the old PC can't be placed on the Internet, then I'm sure Macrium Support will help you if you contact them.  In terms of using an upgrade license, I'm not sure what happens.  I got a free upgrade to V7 because I purchased V6 close enough to the V7 launch, so I just got a brand new key, but I believe paid upgrades require you to provide the previous version's license key.  However, given that you've already activated your V7 license once, you might not have to do that again.  But either way, you start by entering your V7 key when you install it on the new PC.  If you get prompted for a previous version key in addition, then provide it since you have it anyway.  If you don't get prompted, then you'll be all set on V7.