To rephrase:
The configuration protocol can easily see if it is a NAT or not.
Clients MAY request ANY, UDP or Proto-41 as encaps.
When the encaps is ANY the client sends the IP it think it has globally to the configuration server, which compares it with the actual connection origin, different -> NAT -> use UDP. Otherwise it can safely assume proto-41.
Additionally:
Clients MAY also check if they have an RFC1918 address, they then also know that they are behind a NAT.