Brute-force attack on OAEP Assume $M_1$ is $\operatorname{OAEP}$ padded and encrypted and the ciphertext is 1024 bytes as an example. If an adversary somehow gets around the encryption and manages to get half of the bits of $\operatorname{OAEP}(M_1)$, and although infeasible, assume that it was somehow possible to loop through all combinations of the missing 512 bytes. At some point the $\operatorname{OAEP}$ decode will succeed and give $M_1$.

Will the decode operation succeed more than once to give other plaintexts, and if so, how many times?
Skipping over the OAEP details, considering only the probability that a random ciphertext will have a valid all-zero pad.

For a $t$ bit pad, the random probability is $1/2^t$. Brute forcing 512 bytes or $512\times8$ bits will result in on average $2^{512\times8}/2^t$ valid padding. Assuming a $128$-bit zero pad this is$\dots$

$$3.069183e1194$$

As you said this is impossible. Information theoretically we know the message is one of the $2^{512\times8}/2^t$. If you have any additional structure of the message, you may reduce the candidates further.

Another way to look at this is the birthday bound. Where it'll take on average $2^{t/2}$ random samples to find a valid padding.