Do I have to use a media proxy with Kamailio/OpenSIPS for a far-end NAT traversal solution?
Not necessarily, although it may be desirable in various cases for reasons having to do with accounting or topology hiding. Use of a media proxy is strictly necessary only in cases where there is no logical network-layer reachability between the media endpoints of a SIP session. An example would be media passing between a public and a private (RFC1918) address space with no NAT on the private side, and a SIP proxy that is connected to both; there is no way for the public endpoint to address the private endpoint. NAT-traversal fixups revolve around substituting received IP and port information (Layer 3 & 4) in place of that provided by the endpoints themselves. If the endpoints can reach each other at the rewritten coordinates, there is no reason to proxy the media.
