Each game is created randomly (or selected by bnet with some kind of system as it is likely that bnet tries to balance the load among all the servers) on one of the servers. After it is created the game stays on that server until it is destroyed. If you create a new game the server is randomly chosen again.
So to answer your question it's likely that you weren't on the same server on the new game.
Indeed. In these scenario's you are better off rejoining the same game you just left, because as long as you've been in there long enough it'll usually stay alive for a few minutes if you quit, as long as you can get back in there with the other character fast enough.