There is an interesting phenomenon in mathematics called the birthday paradox which roughly says that if you randomly pick from a bunch of possible items, the number of times you have to pick before you get the same item twice is much lower than you would think. I am going to do the math, but you can confidently say that only a few million planets need to be visited before people start to visit the same ones.

There are supposedly 18 quintillion planets in NMS, which is roughly 2⁶⁴ (I use base 2 because I am a computers scientist, and it makes doing the numbers easier).

Now, the game starts you out in specific regions that are far away from the core because they don't want anyone to get to the core really fast, right? If starting points were randomly spread over the galaxy then you could expect that a large number of people would start pretty close to the center, which they don't want. Lets say they want people to be at least 1000 systems away from the core (probably more, but lets go with this), and that each system has 10 planets (also a rough number but we're talking generalities here). That means that there are only about 2⁵⁰ starting systems.

The birthday paradox says that you only need to choose about 2²⁵ things out of 2⁵⁰ before you start to have collisions. That is 33 million. So with those (admittedly pulled out of my ass) numbers, after ALL players have explored 33 million systems, which would happen relatively quickly given the number of players there are, then we would expect two of them to meet, or be close enough that they could engineer a meeting.

Another way to think about this is, individually it is very rare to win the lottery. Pretty much everyone will never win the lottery in their lifetimes. But, every month hundreds of people win the lottery. There are just that many people involved that despite the event itself being very rare, it happens many times over the population. Same thing here, people were bound to meet, even relatively quickly after release, but that does not mean that the universe is small. Most people will never meet another person.