Did uncompressed keys always use the 04 prefix, even before compressed keys (which used 02, 03) came into use?
yes.
Has Bitcoin gone through an update to add these prefixes to various key types?
There are no updates to add prefixes.
However, Bitcoin wallet software has been updated to use these compressed keys. At the time, OpenSSL was used for signature verification and accepted both compressed and uncompressed public keys, so there were no changes to the required consensus rules/implementation. Actually, there is a third type that was (and still is) supported. hybrid Keys using prefixes 06 or 07 (according to even/odd T coordinates), 32 bytes and 32 bytes Y coordinate. I don’t understand the motivation for having such a type, but it is part of the implemented specification.
So these prefixes are included in the hash used to generate the address, so have addresses using uncompressed keys “changed” when compressed keys are introduced?
If these prefixes didn’t actually exist in the first place, it would have been a hard fork to introduce them. Fortunately, no changes were needed.
Of course, wallets switching from uncompressed public keys to compressed public keys had to change their addresses. However, since the sender only sees the 160-bit public key hash, only the recipient cares about the distinction. At consumption time, the recipient must reveal its entire public key, and its hash must match the sent public key hash.
If you have a very old Bitcoin Core wallet.dat file that has never been updated and you load it into the latest Bitcoin Core 27.0 software, you can still go back to the previous version since it uses the uncompressed public key to generate the P2PKH address. Previous version. However, this feature will not continue to work as legacy wallet support is scheduled to be removed from Bitcoin Core. You can still use these older files, but you must first convert them to a newer format.
Additionally, since the introduction of compressed public keys, there has actually been a new address type (with Applicable consensus changes): P2SH, segwit, and taproot.