What is the best way to monitor non-wallet addresses for new transactions The main purpose is to have "payment done" confirmation as fast as possible, within  some seconds.

First option is to implement it myself. Now I have the following implementation based on querying Bitoin-qt from .NET API:
I receive all new transaction IDs using getrawmempool and then iterate through each of them to get details using getrawtransaction to find transactions with addresses I want to monitor.

2 years ago it used to work well, but now I see it performs slower and slower.
So, I think bitcoin-qt + .NET API is not the approach which can increase monitor time.

Another option is to use third-party services, like blockchain.info, which can be used in my (commercial) application.
You can use the importaddress functionality to make the Bitcoin Core wallet (bitcoind or bitcoin-qt) treat certain addresses as its own, even though it does not have the key for them.

This will make them appear in the outputs of RPCs like listtransactions, getreceivedbyaddress, listunspent and getbalance. It will also trigger notifications through -walletnotify and the recently added ZMQ mechanism.