Is there some method how you can calculate the balance of an address without resorting to web-based API's? When I import a private key the rescanning of bitcoind takes hours. I know to get a balance you would need to iterate over all transactions in the whole chain, but maybe there is still some optimization possible.
You would need to use a client node that has a different architecture, from the satoshi's client. Specifically, the client must be able to quickly browse through all the unspent outputs.
You may want to check this table for clients that support Multi-wallet. Among them, there is a new client Gocoin. It is currently in a testing phase, and you need to build it yourself from sources, but if you have a PC powerful enough to run it, it needs less than a second to give you an unspent balance of any standard bitcoin address.