Well I have tried to do this on and off for a little while now and found a post by MaxRabbit that works for me.
My server config is pretty bare at this point:
Server start script:
./srcds_run l4d -secure -maxplayers 4 +hostport 27015 +map l4d_hospital01_apartment +exec server.cfg +sv_lan 0
To connect from a Lobby this is what you do ...
First launch L4D and open up the console and type:
Here x is your WAN IP address and y is the game port (i use 27015).
Close the console and then set your lobby options as normal and the lobby will connect directly to your server!
I am not sure why the sv_search_key way of achieving the same end is not working for me but this will do just fine ...