You might try changing FS2004 to use a different "Connect" port. To change the Connect port in FS2004, click "Multiplayer" on the FS2004 startup screen, then click "Open Multiplayer Session", then on the screen where you type in the IP address, click "Client Settings", and set the "Connect" port to be 23455. Then click OK, and see if you can find external games.
FS2004 uses this "Connect" port, as well as UDP port 6073, but I think you might be able to get away with just forwarding 23455 to your FS machine, and forwarding 23456 and 6073 to the FSHost machine (assuming FSHost is using the default port 23456 for the "2004 Host Port" on the Options / Session window).
Russell