Does RSA padding have to be unpredictable if the payload is?
From what I understand, you consider a scenario in which a fixed, random-looking message $M$ is sent to multiple recipients, encrypted using RSA with some padding (this is called the "broadcast RSA" setting).

Moreover, you consider affine paddings, in the sense that you apply the RSA function to an element of $\mathbb{Z}_N$ of the form $a_i M + b_i$ for some values $a_i, b_i$ depending on the recipient which may be known in part or in full by the adversary (in fact, we even have $a_i = 1$ in the cases you consider, but that doesn't really matter).

In that case, expanding a bit on fgrieu's answer:


No, it is not OK to use a public deterministic padding that depends on the recipient, even if the padded message is as long as the modulus. This type of padding is broken in the broadcast setting by a generalization due to Håstad of the simple CRT attack alluded to by fgrieu.
For the same reason, a predictable padding function will not do, nor indeed any affine padding where the values $a_i, b_i$ are known by the adversary.
Even using such a padding where the $b_i$'s are randomized can be dangerous. For example, a padding of the form $R_i \| M$ (with $R_i$ chosen at random for each recipient and long enough so that the padded message is as long as the modulus) can be attacked in the broadcast setting if $M$ is relatively long: see this paper (the attack is admittedly rather theoretical, but still).
This survey on RSA attacks by Boneh is over 10 years old already, but always good reading (you're especially interested in §4).


Generally speaking, I wouldn't recommend using an affine or polynomial padding function for any new application except for interoperability reasons; and I would especially advise against using a custom affine padding that "looks strong enough" (unless you want to make cryptanalysts happy by providing them with a fresh new target :-).

A better idea (which is essentially what Thomas Pornin suggested in the earlier discussion) is using RSA-KEM (RFC 5990): for each recipient, pick a random element $R_i$ in $\mathbb{Z}_N$, and send $C_i = R_i^e \mod N$ to the $i$-th recipient, together with the encryption of $M$ (with your favorite block cipher) under a key derived from $R_i$.

Other options include paddings like RSA-OAEP (part of PKCS#1 v2.1).