If this is true, the wallet will auto recognize / create a new btc address and pre-determine a deposit address in the wallet before sending btc out?
Yes. When you use a properly written wallet that uses unique change addresses, then the wallet generates the change addresses for you and keeps track of them internally.
So we are totally relying on bitcoin wallets to spend bitcoins? And each time we make a payment, we need to back up a new private key and the old private key will become useless?
In this case, for each transaction we have to perform a backup? For people with paper wallets, if they decide to spend the coins, each time they make a transaction, they need to print out the new keys and store them?
For multi-sign keys, each time we spend balance on that address, we also need to produce and distribute multiple private keys to different ppl?