This entry is a user-made guide and not verified by any eMule developer, but is still a helpfull addition for most users. You you can find questions and comments on this topic in a dedicated thread on our forum.
Let me share with you what I've learned from my successfully fighting "firewalled" status on the Kad network. As most folks reporting the problem do, I run eMule on a Windows host with a private IP, behind NAT.
Thank the Holy Mule, I'm the admin at my site, so I've been able to investigate the problem in detail. The story began as usual: I had opened needed ports on the WinXP host running eMule and forwarded the TCP and UDP ports from my border router to it, but yet my Kad status was "firewalled". To tease me further, it flipped to "open" and back once, when I was not touching my configuration at all. At the same time I was getting High ID on Ed2k.
Later I found that mapping the private IP to a dedicated public IP instead of just forwarding the ports would give me "open" status on Kad instantly. Then I returned to port forwarding configuration and tcpdumped on the internal and external interfaces simultaneously. Imagine my surprise when I saw that my NAT still was translating the source port in UDP datagrams initiated by my eMule, i.e., sent not in responce to a UDP request from the remote node.
That is, port forwarding configuration, at least in some routers, doesn't work in the opposite direction. You may have to configure your NAT additionally for it to keep the UDP source port when your eMule tries to contact a node outside. Keeping the UDP port is crucial for Kad because info on your IP and port is spread over the whole network.
Assume your eMule host is 10.1.1.10 on your intranet and gets NAT'ed to 220.127.116.11 on the Internet. The UDP port initially is 4672.
When your eMule tries to contact a Kad node with IP 18.104.22.168, your NAT translates its IP 10.1.1.10 to IP 22.214.171.124 and port 4672 to port, say, 65000. As long as your NAT keeps the translation entry, node 126.96.36.199 can contact you back at port 65000, too. However, other Kad nodes that have learned about you from 188.8.131.52 will believe that your UDP port is 65000, not 4672. Undoubtedly, they will fail to contact you at this port because the translation entry is valid for IP 184.108.40.206 only.
The solution is to tell your NAT to keep the source port, usually 4672, in outgoing Kad "sessions" (NAT entries created from outgoing UDP datagrams.)
I use PF in *BSD. The configuration now is as follows:
nat on $extif proto udp from 10.1.1.10 port 4672 -> $realip port 4672
nat on $extif from 10.1.1.0/24 to any -> $realip
rdr pass on $extif proto tcp from any to $realip port 4662 -> 10.1.1.10 port 4662
rdr pass on $extif proto udp from any to $realip port 4672 -> 10.1.1.10 port 4672
The 1st line makes sure my Kad port still is 4672 on the outside. The 2nd line does general NAT. The 3rd and 4th lines do port forwarding for incoming Ed2k connections and Kad datagrams, respectively.
Of course, you will need to consult the manual for your router/NAT to find out how to set it up properly.
Hope this helps.