But if you brute force the key, when do you know that you got the right one? Its hard to tell a correct IP address from four bytes of garbage. Depending on the encryption scheme, you are bound to get a lot of fake local IPs - potentially all 256^4 of them.
Of course this assumes that you don't include a checksum or another way of verifying the key. If you do, then you're right, you can just brute force the key. If you don't, then you have another problem: For every node that you connect to, you have to try the local IP you "decrypted" (well, at least if it makes sense in your subnet). This could be a lot of overhead if you have a lot of nodes.
There might also be other sources of entropy that are common to all nodes behind a NAT, for example routing information, or identification strings of the router (most customer routers identify themselves via UPnP). Also you could try to piggyback on other networks, like Windows' workgroups or Apple's bonjour.
Finally, since the public IP is public anyway, you could send the (poorly) encrypted local IP only to nodes that have the same public IP as you do. I haven't thought this to the end and this probably won't work when an ISP gives multiple users the same IP, though.
So, I think it would definitely be possible to implement this, the question is how much effort you want to put into this. In a real application, I would probably just try the broadcast, and if it doesn't work, give the user the option to manually connect over LAN (e.g. by entering a code word on all nodes).
It's much easier to tell a correct private RFC 1918 IP from four bytes of garbage. There are only 17,891,328 valid values.
The odds move further in your favor when you have multiple private addresses to work with -- a valid key will most likely result in addresses that are all in a single RFC 1918 block, and very possibly all in the same /24.
Of course this assumes that you don't include a checksum or another way of verifying the key. If you do, then you're right, you can just brute force the key. If you don't, then you have another problem: For every node that you connect to, you have to try the local IP you "decrypted" (well, at least if it makes sense in your subnet). This could be a lot of overhead if you have a lot of nodes.
There might also be other sources of entropy that are common to all nodes behind a NAT, for example routing information, or identification strings of the router (most customer routers identify themselves via UPnP). Also you could try to piggyback on other networks, like Windows' workgroups or Apple's bonjour.
Finally, since the public IP is public anyway, you could send the (poorly) encrypted local IP only to nodes that have the same public IP as you do. I haven't thought this to the end and this probably won't work when an ISP gives multiple users the same IP, though.
So, I think it would definitely be possible to implement this, the question is how much effort you want to put into this. In a real application, I would probably just try the broadcast, and if it doesn't work, give the user the option to manually connect over LAN (e.g. by entering a code word on all nodes).