They don't do any NAT traversal, but that use UPnP to open ports. During a talk Gunnar Kreitz said that they still got a 60% success rate for connections (if I remember correct, varied between countries also). And that this was good enough for them. More can be read in this paper: http://www.csc.kth.se/~gkreitz/spotify-p2p11/spotify-p2p11.p...