We do not need to check in the database that each output is spent only once.
Note that instead of checking only the outputs, you have to check the source address balances *and* the target address balances. (To see if the new target address balance equals the old balance plus the money transferred.)
Each transaction contains numbers: money transferred; balances of each involved Bitcoin address; time.
The size of transactions is one of the main bottlenecks in practice, since they have to be replicated over the network to every node and stored in the block chain.
A slightly more complex database is a very good tradeoff for faster tx validation and smaller transactions.
Another advantage of the current design is that it allows for complex transaction types (even though that's currently disabled in the official client), see
https://en.bitcoin.it/wiki/Script