How can a new transaction in the beginning ever get an approval rate over 50% if each server first needs to see the transaction approved by some other servers in his UNL?
Before each consensus round starts, servers collect and forward transactions. When the consensus round starts, each validator makes an initial proposal based on what transactions they saw before the consensus round and what transactions didn't make it into the previous consensus round. There's a window with a minimum length of two seconds to give validators a chance to make an initial proposal. Validators can then look at the set of initial proposals to see how many validators are participating in this consensus round and how many of them vote yes or no on each transaction. They use this information to update their proposals to avalanche to consensus.
A server only includes a transaction in his own proposals, if he sees the transactions in other server's proposals. But if nobody starts inlcuding it in his porposals, it never will get a 50% approval rate.
What am I missing here?
Each server's initial proposal is based on its independent opinion of which transactions should go in the consensus set.
https://ripple.com/wiki/Ledger_Cycle