Wallet programming, search transactions by address
You do need to keep a separately indexed database of the blockchain,

insight.is is a good place to start, 

bitcoind would have to do an extensive rescan to answer that query.