Hi Hans,
It sounds like you're doing everything correctly, although you probably only need to open 23456 and 81. The other ports shouldn't be necessary when 23456 is available. (that's something new in FS2004, most other DirectPlay games still need 6073 and 2302-2400)
The fact that FSHostSpy is finding your game ok means that at least port 81 is working ok, so we need to see about 23456.
Can you send me an email, or post here, when you have your server running again? Maybe someone can try connecting to your game, to see if it's working.
You said you could connect to your game with the internal IP but not the external IP. This isn't surprising actually, many routers have this problem -- I think it's called the "u-turn" problem (I'm sure someone can correct me if I'm wrong). So I wouldn't worry too much about that, but let's see if anyone else can connect.
Russell