Your link to the documentation doesn't identify the format methods you are referring to. I'm guessing the deprecated method is formatNumber(String source).
While the general definition of "deprecated" includes the possibly of the feature being deleted at some future time, it has been the Android policy to not delete items from the API that will break existing code. An example of this is AbsoluteLayout, which was deprecated in API level 3, and yet remains a part of the API. In Android, "deprecated" is an indication that there is an alternative, better way to achieve the same result, and you are strongly encouraged to use it instead (if possible).
Here, the improved alternative method is only available in API level 21. To support devices with lower API levels, you can safely used the deprecated method. It's not going away anytime soon.
Another option is to examine the source code for PhoneNumberUtils
to see if you can use pieces of it to create your own formatNumber()
method that does what you want and supports API 16 -- probably not worth the effort.