Co-op isnt working if your NAT is strikt. All you can do is join someone with an OPEN nat, not hosting or playing private with a friend.
What I've tried so far:
Opened ALL ports combined from all the threads on this forum mentioned, and the ports are open for real I know what I'm doing.
Disabled firewall on the Router and enabled UPnP.
Disabled my firewall on my computer totally.
Disabled my anti virus.
Made a service for the port on my network from windows.
I run everything (origin.exe and deadspace3.exe as an administrator, and everything is up to date)
Tried different compatible modes with both .exes with no success.
I've hosted websites and game servers before and all I had to do was port forwarding, and that worked out perfectly so this is clearly something wrong with this game only.
I won't flame on EA for this but you should really fix the connection build, since it's terrible. Shouldn't be to hard for you guys?