So far I thought that Skype calls always had to go over a relay computer in the network when both ends of the connection are behind a NAT router. Turns out that this is not the case at all.
When monitoring the establishment of a Skype call it can be seen that during call establishment Skype tries quite hard to find out how the UDP port mapping is done by sending UDP packets over many ports simultaneously and if there is a way to get through the NAT directly (e.g. with UPnP and also with the NAT Port Mapping Protocol NAT PMP). At the same time the protocol also seems to try to find relay nodes over which the voice and video traffic could run in case the NAT scheme can't be figured out. In case a direct channel between the two end points can be established the other end is alerted of the incoming call and the direct link between the two parties is used.
I was successful to establish "direct" calls between two computers that were behind two NAT DSL routers and also with one computer behind a DSL router and the other one connected to a public hotspot of a nationwide hotspot provider. When using a VPN tunnel, however, Skype could not establish a direct link and had to fall back to channel the voice packets over one relay in the network. The same IP address was used as destination address on both ends, i.e. exactly one relay was necessary.
In that regard, the number of relays shown in the call technical info does not reflect that. The technical info often showed 4 relays when in fact the call was direct or only going over one relay. So perhaps this relay indication is something else entirely?