Phone number brute forcing protection in web

I recently started designing my own Web-API and my current goal is to make it possible to register guest user with his phone number, but there is a requirement: my database must not contain phone number duplicates. So I decided that I need a service for validating this case. That's where I felt a little bit confused.

Let's suppose I have one REST-service which checks whether entered phone number exists in system.
It consumes phone number (like +7-913-XXX-XX-XX) and produces boolean value depending on phone number presence/absence in database.

If I implemented this logic it'd be really naive, so I'd be able to send as many requests to this service as I want and find out real numbers related to this system. As a conclusion, data will be compromised some day.

The way of blocking particular IP-address (due to high RPS from one machine) obviously does not seem to be a best solution because there are ways to make it through different IPs.

My questions are following:

1. Have I missed any concept in my goal (wrong direction or smth)? How should I check phone number in another way if it's required to check it in database?
2. If it's okay, is it even possible to avoid kind of this brute forcing so my data (not only phone numbers but any personal data in general) will be kept safe and sound?
3. If not, are there any general ways to make brute forcing not so easy? (except the way above)
4. How do Java-developers deal with it? Can Spring-framework help in this case, by any chance?

Answer from Synchro helped me coming up with following scenario for my situation (for me it seems fair enough in terms of brute forcing during user registration):

1. Guest enters "Register button"
2. Guest enters phone number
3. Verification code is sent to this number (no matter whether it exists in db or not)
4. Guest enters verification code from his phone.
   • If verification code is wrong -> error;
   • If error is made N times -> error without permission to continue process ("limit is exceeded. Try again" or smth);
   • If Verification code is ok, then user recieves appropriate token and system may create some data to identify this session as something unique
5. Now we have some permissions and find out whether verified phone number exists
   • If it exists, offer some "what to do next" - options (recover password, for instance)
   • If it doesn't, provide blank to fill personal data and register user

I know I missed lots of steps and validation stuff, but I got the key concept: verification should be done first, and only afterwards we allow only this phone to be checked in system somehow.