There might be a clever way to discover the probability (especially since every node can communicate with every other node) but I couldn't figure one out. However, here is a theoretical way of getting the probability. I say theoretical since no computer could actually do this process for anything other than small $n$. That being said, this process would theoretically work if every node does not communicate with every other node (which might be handy for other applications).
There are a finite number of possibilities that can occur before every node has been reached at least once. However, this number is extremely large. Here is one possible way of enumerating each possible state. Consider a bit string of $2n$ digits, each of which can take the values $0$ and $1$. The first $n$ digits state whether a particular node has been communicated with before. The second $n$ digits state whether a particular node was communicated with in the previous round. For example, with $3$ nodes you would read
$$(101,100)$$
to mean: Nodes $1$ and $3$ have been communicated with in any previous rounds and node $1$ was communicated with in the previous round. Thus, there are on the order of $2^{2n}=4^n$ possible states for $n$ nodes. This number is not exact as certain states are impossible to attain (like the all $0$s state) but it is a good upper bound. For a lower bound, note that there are at least $2^(n-k)$ states since there will always be at least $k$ states that were communicated with the previous round (except for the first round) and the remaining $n-k$ nodes all are either on or off. Either way, there are an exponential number of finite states in $n$. So for the example given, there are at least $2^{500-25}=2^{475}\approx 9.76\star 10^{141}$ (Like I said, no computer could actually do this). Of particular note, the state
$$(11...1,...)$$
signals the end of the game as every node has been communicated with in some previous round.
The process: Since we have a finite number of possible states, we can use Markov Chains to find the probability that any particular state has been reached after $m$ rounds. That is, we need to find
$$P(\text{first $n$ digits are all $1$ after $m$ rounds})=\sum_{i=0}^{2^n-1}P((11...1,[i]_2)\text{ after $m$ rounds})$$
(here, $[i]_2$ is the binary representation of $i$). However, let me reiterate again how impossible this is to do for any large $n$. This would require:
$-$ Multiplying a $4^n\times 4^n$ matrix $m$ times and reading $2^n$ entries (upper bound)
$-$ Multiplying a $2^{2n-k}\times 2^{2n-k}$ matrix $m$ times and reading $2^n$ entries (lower bound)
For example, for $n=3$ and $k=1$ (which corresponds to a $64\times 64$ matrix), we find that the probability of of succeeding after $m$ rounds is $1-2^{1-m}$. This answer could actually be found fairly simply without the process outlined above. However, this is because $k=1$. For $k>1$, the probability becomes much more complicated to figure out. In general, the $k=1$ problem is equivalent to the Coupon Collectors Problem.
