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.
This is probably not a full solution, but maybe a possible optimization. Since you send all BTC out of the address in every send transaction, you should only have to look at the transactions that happen after the last sending transaction to calculate the value at an address.