How does adding another 9 to a phone number that can only start with either 8 or 9 make more phone numbers possible? Here in Brazil, Anatel (an institution that dictates how phone carriers should operate) has ordered that every phone numbers in the states of the Southeast (which is actually the southwest) must add an extra 9 to its already existing numbers in this fashion:

9xxxx-xxxx

But the problem with this (in my head) is that the second number (formerly the first) is always either 3, 8 or 9, the number that is being added before is always 9, and all the phones that could be taken are already taken (from third digit 1 to third digit 9). In the 70's, the limit of how many numbers a phone number could have were changed from 7 (xxxx-xxx) to 8 (xxxx-xxxx), meaning that new numbers could exist (3xxx-xxxx, 8xxx-xxxx and 9xxx-xxxx). How does adding a 9 to already existing and taken numbers increase how many numbers can be registered?
(I don't know which tags I should use, since this is such a simple question)
 A: I have no personal knowledge of the Brazilian telephone numbering system, but I can tell you what happened in Singapore, and maybe the same rationale applies.
Before $1995$, telephone numbers had just seven digits.
Pagers had become really big by then and mobile phones (cellular phones) were just starting to crack the market. So a '$9$' was added to pager and mobile phone numbers to distinguish them from landlines. This automatically allowed (with just that fixed prefix) $10^7$ theoretical possibilities for the mobile devices without any collision with fixed landlines.
In $2002$, landlines had a '$6$' prefixed to all of them. The rationale for this is less clear to me (for pretty much the same reasons you mentioned), but I can think of two non-mutually exclusive possibilities:
1) to immediately and clearly distinguish a fixed line from a mobile device.
2) to cater for projected expansion in numbers by allowing prefixes other than '$6$' (or '$9$') for new landline subscribers (anticipating increased immigration). This reason may be applicable to your question.
As it turned out in my country, I think they were being a little optimistic if their main driver was reason 2). Even though there was a big population increase, the number of landline subscribers has not really gone up proportionately. A lot of newcomers would rather just stick to mobile phones.
Further changes were made: An '$8$' prefix was added for newer mobile lines and '$3$' was added to cover new VoIP lines. So you see, adding prefixes does help to expand the number repertoire they can use, provided they're not sticking to just a single prefix digit.
A: If you add a new digit to the beginning, you now have a 9-digit number.  It sounded like all numbers before had fewer than 9 digits.  Therefore all 9-digit numbers should be not yet taken.
A: I do not believe that the purpose is to add more numbers (that is to increase the number of combinations available for users to register) but rather to avoid misplaced calls.
That is, by adding another (pseudo)digit-I call it pseudo exactly because it does not alter the maximum amount of combinations-you create a "safe mechanism" for the system to correct any mistakes during the placement of the call. If the system "reads" one number wrong it might lead to another call-but reading two numbers (your two $9$s) is less probable, thus leading to far less misplaced calls.
This is more relevant to coding theory and error correction, and the way telecommunication systems work, it has nothing to do with the max of numbers available.
