Is it not possible to use a Bloom filter, to enable querying full-nodes about titan transactions with addresses that would be of interest? That way the wallet would only need scan those transactions that are reported to it.

nop .. you have to try to decrypt every single transaction memo you can find and see if you succeed .. if so, it's your transaction, if not you can continue. So it would be required to have the memos and the private keys on the same system for decrypting

I think there should be ways (with current blockchain features) to implement something like what julian1 is talking about. Here is my attempt at it (please correct me if you see mistakes in this design, particularly about the privacy conclusions):

You still have the 19 original bytes for the encrypted memo, actually make that 18 to put a special character at the end of the first encrypted 32 bytes to designate that is the end of the official memo text. The remaining 32 bytes of the memo will instead not be encrypted. Put a special character at the beginning of these 32 bytes to designate to anyone publicly looking that this is most likely special add-on information and not just encrypted data that is part of the memo, and then put another byte after that to specify the protocol, and specific version of the protocol, to follow for interpreting the rest of the memo data. This leave 30 bytes of data to work with.

The first 4 bytes will be an encrypted version of the recipient's registered account ID. It is encrypted by XORing the ID with the last 4 bytes of the hash of SECRET (which is calculated from EC multiplication of the one-time private key and the recipient's public key, or alternatively EC multiplication of the one-time public key and the recipient's private key). This means that if the recipient receives the one-time public key of the transaction along with these 4 bytes (called RECIPIENT_ID_ENCRYPTED_FOR_RECIPIENT), they will be able to find out whether the transaction was likely intended to them (with some false positive rate of course).

The next 4 bytes will be another encrypted version of the recipient's registered account ID (called RECIPIENT_ID_ENCRYPTED_FOR_SENDER). In this case it is encrypted for the sender. This is just an optional bonus feature to make recovering outgoing transaction histories easier for a user. It is encrypted by XORing the ID with the last 4 bytes of the hash of the one-time private key. This means that if the recipient suspects that a transaction was sent by them, they can scan through the indices sequentially to compute the hardened child keys of some well specified descendant of its account's owner private key, find the private key corresponding to the transaction's one-time public key (thus proving the outgoing transaction is one they created), using the hash of that private key to recover the decrypted recipient ID, look up that ID on the blockchain to get the active public key of the recipient at the time of the transaction, and then do EC multiplication of that public key and the one-time private key to calculate SECRET and thus decrypt the memo. Since the selection of one-time private keys to use in each subsequent outgoing transaction by that account can be derived from an incrementing index, and since all outgoing transactions by that account can be collected in order (just find all transactions spending balances that the account received through income transactions), it should be very fast to decrypt all the outgoing transactions.

The next 20 bytes are the last 20 bytes of a hash of a hash of a special common secret, called the OBSERVER_SECRET. Each registered account can optionally register an observer in its public account record (this can simply be the registered account ID and/or active key address of the observer specified in some field in the public JSON), which is what causes the sender to use the protocol I am describing in the first place. It is important for privacy for users to pick observers that many other users also pick (I imagine there would only be a handful of used observers who would probably also act as the light wallet servers). The sender does EC multiplication with one-time private key and the observer's active public key to get OBSERVER_SECRET. An observer scanning through the blockchain can pay special attention to transaction that seem to follow this protocol in their memo. They will calculate OBSERVER_SECRET (from EC multiplication of their active private key and the transaction's one-time public key) and compare the last 20 bytes of the hash of the hash of OBSERVER_SECRET to the appropriate 20 bytes in the memo transaction. If it is a match, they will then use OBSERVER_SECRET to decrypt the remaining 4 bytes in the memo field, which I will talk about next.

The remaining 4 bytes in the memo field are an encrypted version of 4 bytes called FILTER. They are encrypted by XORing FILTER with the last 4 bytes of the hash of OBSERVER_SECRET (so both the sender and the observer can encrypt/decrypt it). FILTER is split into two parts: the first part is a sequence of bits that communicate how many bits, N, will be used for the second part, and the second part is the last N bits of the hash of the transaction recipient's address. N can range anywhere from 0 to 31. Given a particular value of N, the first sequence of bits will consist of (31-N) ones followed by a single zero. This allows the observer to unambiguously determine from the 4 bytes what the value of N is as well as get the N last bits of the hash of the recipient's address. My guess is that at any given time, there will be wide consensus on what value of N to use. For example, if there are M registered accounts, it would probably be smart to use something like N = max(0, floor(log(M)/log(2)) - 3) to ensure an appropriate number of collisions for the sake of privacy. At the same time, it is not desirable to have too many collisions because that requires the recipient to scan through many more transactions that do not belong to them. The observer takes the transaction hashes/ID as well as the one-time public key and the RECIPIENT_ID_ENCRYPTED_FOR_SENDER of the transaction and stores it as a value in a database where FILTER is the key.

Now if a user wants to recover their transaction history using own their wallet master key, they will first send their account's address to their previous observers (which is recorded in the blockchain) along with proof that they are the holder of the account's private key so that the observer can provide even better privacy to their customers. By the way, if the observers disappear, the user is forced to do a full scan of the blockchain (at least for the periods in which the observers who have now disappeared/gone bankrupt/retired were registered for the account). In addition to the address, they also send the interval of N (for the FILTER) that they are interested in; this allows them to starts with large N and only work their way down to smaller N (which means more transactions to check) if the user thinks there are funds still missing or wants to be extra sure. The observer returns a list of tuples (transaction hash/id, one-time public key, RECIPIENT_ID_ENCRYPTED_FOR_SENDER). The user scans through the list and filters out the tuples that it knows cannot apply to them. For each of the remaining tuples, the recipient requests (through the transaction hash/id) the full transaction for the blockchain. The user can then filter any of these transaction that were actually false positives.

Furthermore, assuming everyone was consistent about the formula for N, it would be easy for the user to reduce the interval of N to minimize the number of extra (false positive) transactions without really compromising privacy. The user could also specify a time filter, in which the observer did not return any transactions that occurred outside a specified time window (the interval between last time the user polled for new transactions and the present time, for example). This would further reduce the number of extra transactions that need to be returned. However, if a user makes the time window too small centered around the time they know a transaction should arrive, then that compromises the user's privacy with respect to the observer (but fortunately not with respect to outside third parties), since the observer can assume of the possible accounts that map to a particular FILTER of a transaction, it is more likely that the accounts that actually asks to receive transactions that have that FILTER within a time close the transaction time are the true recipients of the transaction rather than those who make the request later. Also if the observer is also the same entity as the light wallet server (the entity that the user will be requesting the full transactions from anyway), then there isn't much gained in terms of privacy from the observer. But the point is that the user still has privacy from third-parties and also has plausible deniability with respect to the observer (meaning in theory the user could be requesting transactions that have nothing to do with them just for fun / increasing privacy).