Let i be the smallest number in use, and assume that i is at least 0001. For any other phone number k in use, k is a gray pigeon occupying hole number k and k - i is a white pigeon occupying hole number k-i.
There are 5000 gray pigeons and 5000 white pigeons (10,000 pigeons) occupying 9999 holes numbered from 1 to 9999. Two pigeons occupy some hole j. It's easy to see that two white pigeons or two gray pigeons can't occupy the same hole, so one is gray and one is white. The gray one is phone number j and the white one is k-i = j for some phone number k. But then i and j are two phone numbers that add up to phone number k.