Providers use Carrier Grade Nat, you can't just use the opened tcp port as udp port, as the NAT-Device makes the assignement of the ports.
You'd need a udp listener on the server. On connecting, the game must send a connection request to the udp server port, to get the offical udp source port of the client and keep the client/server connection up to use the same port as udp game port again. When the connections between players is done, the dummy connection between server and client can be destroyed.
So you'd have to dll inject game (awwwwh ) and also in server (easy going).
Yes, the server must listen on a random UDP port for that and the game needs updates too, it's tricky But you have no other choice (except using a VPN, but that's not really a good solution).
But more and more providers put their users behind NAT because of the ipv4 exhaustion. Most of the time you end up behind a "PortRestrictedCone" NAT where the public port doesn't match the source port.
If it turns out that Red Alert 2 can't handle such cases then it's a bigger problem. It should be easy to update the server to handle such cases though, from what I know, Red Alert 2 is using random source ports, that means the server actually has to share not only the ip, but also the port of each player.
The server could override the port and share the public port instead.
Everything looks like it's all about NAT problems, you guys should at least run a test and paste your results in here. Maybe it's something else, but it's impossible to tell without running tests