Do I need to scan the whole blockchain to determine a balance? My understanding of how the blockchain works is that to determine the balance of an address one must find all the transactions that have outputs to that address. So, the only way to be sure you are not missing a transaction is that you have to scan the whole blockchain to determine the balance of an address.

Is that correct?
That is correct. This is what the optional -rescan flag does to the addresses in your wallet when launching bitcoind. 

There is no balance property. Balances are just the total values added up on all unspent outputs for a given address, and the only way to determine the unspent outputs of an address is by scanning/tracing/following each output from address to address.