Why is padding the plaintext with a random string before encryption worse than OAEP / PKCS#7? I'm reading about OAEP / PKCS padding used for PGP to turn deterministic algorithms like RSA from deterministic encryption to probabilistic encryption (randomness in the resulting output). That way the same input encrypted with RSA should produce a different output each time.

However, the wikipedia page for probabilistic encryption addresses a seeming simple solution but doesn't give any details what is wrong with it:


  An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes. Techniques such as Optimal Asymmetric Encryption Padding (OAEP) integrate random padding in a manner that is secure using any trapdoor permutation.


Can someone explain (to a beginner) what is insecure about random padding being added?

In addition, for PGP encryption using RSA, my understanding is that a random nounce / AES key is generated and encrypted using RSA. Then that AES key is actually used to encrypt the source text.

So, if the whole AES key is random to begin with (and required to know anything about the encrypted text) - what exactly is OAEP adding?
The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding 

00 || BT || PS || 00 || D

where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal to 0x02, the padding string (PS) is at least 8 long and consists of random non-zero bytes, the single 0x00 is added followed by the actual data being encrypted (D), and so that the total length equals the effective length in bytes of the modulus.  

The padding can then be uniquely removed because the start of the RSA-decrypted block should follow this pattern that we can check, and we strip random bytes until we meet the first 00, after which we have the data.

The problem lies in implementations that check this padding and that somehow leak (e.g. by the different possible error responses, or time used for checking etc.) how exactly the padding removal failed (no start 00, no 02 byte, padding too short, data unexpected length..) and attacks were developed based on that (see Bleichenbacher oracle etc.). So the padding does work, but it is "ad hoc" (it has no proof of security) and it's too easy to do the checking in a wrong way. Hence OAEP, which has more of a theoretical basis.