Steamworks server browser "Failed to respond"

Hello all,

I’m at my wits end with this problem that has already tried to derail my project. No one seems to have any solution and no one seems to have encountered this, so Epic devs and others alike, please help.

I’m trying to setup a server browser with Steamworks and the OnlineSubsystem. Everything works great under LAN, but when tested with my friend in another continent, no sessions are found.

At first we were using the GameServer API (bUsesPresence=false) and we got these messages:

[2015.07.27-22.02.54:509][931]LogOnline:Display: STEAM:  "gamedir" "boxmanbegins" 
[2015.07.27-22.02.56:992][ 80]LogOnline:Display: STEAM: Failed to respond IP:MYFRIENDSIP
[2015.07.27-22.02.56:992][ 80]LogOnline:Display: STEAM: Server query complete '0' eServerResponded (Server success)

Then we started using the Lobby system (bUsesPresence=true) and had no luck again, getting these messages in the log.

[2015.07.28-21.22.41:560][113]LogOnline:Display: STEAM: Starting search for Internet games...
[2015.07.28-21.22.42:043][142]LogOnline:Display: STEAM: Found 0 lobbies, finalizing the search

We then tried to direct connect using the console command open MYFRIENDSIP and even that didn’t work. We got this message:

[2015.07.28-21.26.08:505][522]LogNet: Browse: MYFRIENDSIP//Game/BoxmanBegins/Maps/BMFrontEnd
[2015.07.28-21.26.08:505][522]LogInit: WinSock: Socket queue 32768 / 32768
[2015.07.28-21.26.08:505][522]LogNet: Game client on port 7777, rate 10000
[2015.07.28-21.26.08:505][522]LogNet: GetLocalNetworkVersion: GEngineNetVersion: 0, ProjectName: boxmanbegins, ProjectVersion:, InternalProtocolVersion: 8, LocalNetworkVersion: 2980932986
[2015.07.28-21.26.14:063][855]LogNet: Browse: MYFRIENDSIP//Game/BoxmanBegins/Maps/BMFrontEnd
[2015.07.28-21.26.14:063][855]LogNet: UNetConnection::Close: Name: SteamNetConnection_0, Driver: PendingNetDriver SteamNetDriver_1, PC: NULL, Owner: NULL, Channels: 2, RemoteAddr: MYFRIENDSIP:7777, Time: 2015.07.28-21.26.14
[2015.07.28-21.26.14:063][855]LogNet: UChannel::Close: Sending CloseBunch. ChIndex == 0. Name: ControlChannel_0
[2015.07.28-21.26.14:063][855]LogNet: DestroyNamedNetDriver SteamNetDriver_1 [PendingNetDriver]
[2015.07.28-21.26.14:063][855]LogExit: PendingNetDriver SteamNetDriver_1 shut down

So now I’m completely at a loss. Firewalls are down, ports are forwarded, I’ve tried nearly everything, to no avail.

I’m open to anything, just please help!