Since I'm NATing my network and don't allow UPnP the statement that they don't do any NAT traversal seemed suspicious since I know spotify does stream to other peers from my machine (400 MB since last reboot (13 days)).

Got the answer from the paper: When a client wishes to connect to a peer, a request is also forwarded through the Spotify server asking the connectee to attempt a TCP connection back to the connecter. This means that as long as one of the two peers can accept incoming connections, the connection will succeed.