How can a recipient recognize which encrypted messages are intended for them? Let's say there's a decentralized email service where parties' public keys are known. A sender sends a message to a recipient by encrypting via RSA with the recipient's public key and posting the ciphertext publicly somewhere where everybody can see, e.g. a public blockchain.
Senders don't want others to know which addressees they're communicating with, so they only publish the ciphertext. Then everyone needs to scan the blockchain for new events and try to decrypt each message with their private key (in the RSA-AES hybrid scheme, they will try to decrypt a one-time AES key the message is encrypted with). If they succeed (and let's say the prefix of the recovered message is their public key per protocol), it means the message is intended for them.
The above scheme requires every participant apply RSA decryption to every message, and the number of messages per time unit are expected to increase. Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?
One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages. This way, each revealed bit splits the number of potential recipients in half (starting from everybody when 0 bits are revealed and halved with each bit), while still not allowing outside observers to determine the exact recipient, but it does allow everyone else to save computing cycles skipping exponentially larger amount of messages.
However, I'm interested to know whether there are even better approaches.
Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?

It doesn't appear that the problem of recognizing the message (without leaking who the message is for) can be significantly faster than public key decryption.  Let me be more precise; suppose we had a way such that:

Alice can publish some public information
Bob can use this information to generate a 'tag'
Alice can check to see if this tag was generated with her public information
No one without Alice's private information can do so (if not, anyone can check if the tag was flagged to be of interest to Alice).

If we have a primitive that can do that, then Alice can use that primitive as a public key encryption method; the method isn't very efficient (in the simplest case, Bob would generate a series of 'tags', where each tag encodes a bit - one bits are tagged with Alice's information, and zero bits are not); however it is sufficient to indicate that the problem isn't inherently easier than the general public key encryption problem.
So, what can we do?  Well, the best I can suggest is use a public key encryption method that's more efficient than RSA; here are two ideas:

ECIES; here, the decryption operation is a point multiplication (and a handful of symmetric operations); significantly cheaper than RSA

NTRU; this is a NIST postquantum level 3 candidate with (to use a technical term) honkin' fast decryption; for example, the ntruhps2048677 parameter set is listed as using only 59,729 Haswell cycles.


Of course, you could also separately RSA encrypt the message along with the tag; however, given that by validating the tag, you've essentially done most of the work, you might want to just use ECIES or NTRU.
Also, one comment on your idea:

One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages

Does that mean that, in the ciphertext, you expose k bits of the public key, where k gradually increases as the number of messages increases?  Well, one problem with that is, while an eavesdropper can't generally be certain who the message is for, he can be pretty sure who it is not for - that many be just as bad...