Paraworld shows the LAN IP ingame (at least for me). As you probably know, you need to give out your router's IP, which you can check on sites like http://www.whatismyip.com/
. I had the problem that I wasn't able to play MP at all because of Hamachi - uninstalling it solved the problem.
Are you sure that you forwarded the port correctly in your router to your LAN IP? You actually only need 1 TCP-port (Default is 1905). The "Internet Multiplayer" option is broken btw and won't work (it will in fact let your game crash), so you need to use play by TCP/IP.
Judging by your description, none of these points should be new for you. But I have no idea atm what else could cause your problem.