Setting up a mirror: can't find remote server
I'll post my own answer to this.

What I did wrong and this should have been very obvious, but apparently I missed this. 
The command: ALTER DATABASE [xxx] SET PARTNER = 'TCP:\....:7023' Should have been run first on the mirror and second on the principal.

So in the end, my networking was, indeed, fine, but a blatant mishap when initiating mirroring on my part.