Also, this: "All the network nodes try to decrypt the message with each of their public keys" ... won't scale.
... The equivalent scaling problem you mention applies with regards to the network checking normal transactions as the useage ramps up.
Assuming you have enough memory to store all your public keys in a hash table in memory, there is no scaling problem with normal transactions. Since the TxOut contains the public key (well, the hash of the public key), it is constant time to figure out whether or not the TxOut is your public key. You do NOT have to loop through all your public keys to see which one matches.