I just want to correct one little thing; excuse me for being nit-picky, I'll shut up after this:
@s{quotedtext}
@s{quotedtext}
@s{quotedtext}
@s{quotedtext}
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.