If you are both using Windows, can you connect in the Classic version of the game?
If you use Discord, you could try invites through that program.
LAN may also be an option, but since you are not on the same local network, it would require VPN software, such as Hamachi or Tunngle.
Try doing a clean boot and then test the game. Click Start, or hit WinKey-R, type in msconfig and hit enter; in the General tab, click Selective Startup, uncheck Load startup items (if required) and leave Load system services and Use original boot configuration options checked. Next, click on the Services tab, check the box to Hide all Microsoft services, then click the Disable All button (maybe make a note of which are currently enabled/disabled), then click OK and reboot the computer.
Run msconfig again to switch back to the normal boot configuration.
Try creating a new Windows administrator user account, switch to that account and see if that makes any different when hosting/joining a new game in a new profile.
Are you both using the same ISP, or living in the same region? If this issue is network related, there would presumably be something different between the two of you compared to the connection between either of you and others you've tested hosting/joining with.
