PGP and openPGP use different encryption algorithms. As I understand, PGP uses IDEA to encrypt a message, then RSA to encrypt the IDEA key. If openPGP doesn't use IDEA, how can it read PGP-encrypted messages?
PGP is the application which implements OpenPGP standard and adds some proprietary extensions. Consequently, as any other standard-compliant application it can interoperate with other applications which comply to the same standard.
Practically there exist old versions of PGP software which are limited in algorithms and features they support. Eg. PGP 2.6.3 used IDEA and RSA keys, while PGP 6.5 used CAST by default and Elgamal keys (if memory serves). But both these versions are outdated.
Modern versions of PGP and other OpenPGP-compatible software support probably everything the standard offers (i.e. all algorithms).
Your understanding is partially correct: if some implementation doesn't support the algorithm used in encrypted or signed message, it will fail to process this data. But as said, modern implementations (of PGP, GnuPG, our SecureBlackbox etc) handle all algorithms so problems happen only when it is old PGP used to process data encrypted or signed using modern implementations.
PGP (the commercial product) and GnuPG are implementations of the PGP concept: that asymmetric encryption can be efficiently implemented by symmetrically encrypting data and then asymmetrically encrypting the symmetric encryption key. OpenPGP is the published specification. The oldest versions of the PGP implementation supported RSA around IDEA and the specification was evolved from the implementation.
To interoperate and allow for updates to algorithms, the software is designed with abstraction and the message format with reserved header fields to tell software implementations what algorithms were used. You want to start looking at Section 5.1 of RFC 2440.
Eugene's answer mentions some historical algorithmic details and covers the version evolution details.
Short version: because of a shared specification, interoperability issues only exist between algorithms selected or backwards-compatibility issues. Modern versions of PGP and GnuPG support many overlapping protocols. Since generated keyfiles list supported algorithms, anything should interoperate with the receiver if your software was able to encrypt a message without error.
It seems to me one important question is whether you can open old PGP encrypted files. If the algorithm that was used to create it is no longer in the current PGP software it won't open. I have a similar situation, using PGP on either Windows 3 or Windows 98. In addition I can't get PGP6 won't properly install in Windows 7.
It comes down to this. An old encrypted file can only be read if it is periodically decrypted, opened and re-encrypted with a current algorithm.