At most $21523361$ phone numbers can be selected, and there is only $1$ way to select this amount of phone numbers.

Consider the situation when the phone numbers have $n$ digits instead of $8$. We shall prove the following by induction: at most $\frac{9^n + 1}{2}$ phone numbers can be selected, and there is a unique way to select the phone numbers, which is to choose all phone numbers whose sum has the same parity as $n$.

When $n = 1$, we can choose at most one phone number from each group
$$(1, 2), (3, 4), (5, 6), (7, 8), (9).$$
Thus, at most $\frac{9+1}{2} = 5$ phone numbers can be selected. Clearly, the only way to select $5$ phone numbers is to select all odd numbers $1, 3, 5, 7, 9$.

Assume the case $n-1$ is true. Consider the case $n$. For those phone numbers not starting with the digit $9$, we can pair them up such that $\overline{a_1a_2\cdots a_n}$ and $\overline{(a_1+1)a_2\cdots a_n}$ belong to the same pair if $a_1 = 1, 3, 5, 7$. Clearly, at most one phone number can be selected from each pair. Also, for the remaining phone numbers starting with $9$, we can remove the digit $9$ and regard this as the case $n-1$. By the inductive hypothesis, we can select at most $\frac{9^{n-1} + 1}{2}$ phone numbers from these. In total, we can select at most
$$\frac{8 \cdot 9^{n-1}}{2} + \frac{9^{n-1} + 1}{2} = \frac{9^n + 1}{2}$$
phone numbers.

To choose this amount of phone numbers, since we need to select $\frac{9^{n-1} + 1}{2}$ phone numbers from those starting with $9$, by the inductive hypothesis, the only way is to select all numbers $\overline{9a_2\cdots a_n}$ with $a_2 + \cdots + a_n \equiv n-1 \pmod 2$. Equivalently, this means $9 + a_2 + \cdots + a_n \equiv n \pmod 2$.

All numbers $\overline{8a_2\cdots a_n}$ with $8 + a_2 + \cdots + a_n \equiv n \pmod 2$. Then by using the first pairing, we find that all numbers $\overline{7a_2\cdots a_n}$ with $7 + a_2 + \cdots + a_n \equiv n \pmod 2$ should be selected, etc. In the same way, we find that all numbers with sum congruent to $n$ modulo $2$ should be selected. Clearly, the condition is satisfied if we only select those numbers. Also, as exactly one number from each pair is selected, there are $\frac{9^n+1}{2}$ such phone numbers. This proves the inductive step.

When $n=8$, we can select at most $\frac{9^8+1}{2} = 21523361$ phone numbers.