How to get instant notification of any Bitcoin transaction involving a specific public address as recipient without knowing the wallet or private key Everything is in the title... For instance, Blockchain can do this if you import a public address and you set up their notification mechanism.

Is there a way to do this in an intelligent (=efficient) way with bitcoind even with some patches? Or is the only solution is to get all transactions and filter for the public address?
If you want to do it via bitcoind, since the transaction in question isn't an in-wallet transaction, this is as close as you can get with bitcoind: GetPublicTransaction()

If your daemon has its transactions indexed (is -txindex enabled), you can iterate through all blocks using getblockash and getblock, then iterate through all the transactions for each block using getrawtransaction and look for outputs and inputs referring the address(es) you want, when it's an input reference then balance decreases, when it's an output reference the addresses balance goes up. 

Obviously this approach will take ages in you need to scan the whole blockchain that is getting bigger every day so you need to limit your iterations to the new blocks only, and for newly added addresses to watch you should allow a few minutes for the blockchain to be rescanned if you wish to provide historical data for them.

Apart from that, there is some talk going on about adding support for watch-only wallets (which is what you're actually asking here) in the core client itself, however this enhancement is not yet available today.

You can also sign-up for http://www.blocknotify.com/ and get a notification every time something changes in that address.

Finally, you can parse the local blockchain files manually but that's a little bit more hard-core, this is a nice post giving some guidance on that: http://codesuppository.blogspot.gr/2014/01/how-to-parse-bitcoin-blockchain.html and an open source project that could also help: https://github.com/jeffchan/blockchain-parser