The problem is the way IM (and other) programs are designed. File transfers embed the user's IP address into the packet, so the other end receives your PC's private IP address, rather than the public IP address that their client could reach. Any solution out there is really a bit of a hack to allow something that was never envisioned...
ReAIM is an AIM/MSN proxy that modifies the IP address so the other end connects back to your public IP, and ReAIM passes it back to your PC.
Check out upnpd too, a partial implementation of MS' UPnP. UPnP allows PCs to dynamically change the routing configuration though, so it's a bit of security issue (especially once trojans and viruses start doing this). Supposedly there's a new spec for UPnP coming out that provides more security...
pseudoicsd too, which I think upnpd is based on.
Most of those are designed for iptables though, which means they won't work out of the box with SME =< 5.5. With ICQ, you can specify which ports the client uses for that stuff. You can forward a range of ports to each user, and specify in the client to use that range... That's basically a static version of what UPnP does dynamically.