Non-existing URLs redirect to "searchguide - level 3" in Safari

I typed a URL in Safari to check whether a domain name had been registered or not, and was redirected to this page:

(here I made the test with "http://fegiuebnfuybzh.com", a random string of letters and a domain I believe no one owns).

The URL I was redirected to is:

http://searchguide.level3.com/search/?q=http%3A//fegiuebnfuybzh.com/&r=&t=0

I couldn't find much recent information about this website, and I definitely never gave my computer access to this service knowingly.

I can see that the home page has a "settings" link:

I do not want this service to be present in my computer at all, even with "off" settings, so this aren't what I'm looking for.

How can I make Safari display the regular "the address couldn't be found" text page, and get rid of this nasty "level 3"?

One reason could be that you are using Level3’s DNS servers (4.2.2.1 through 4.2.2.6) which will redirect you to their search engine for any unknown domain name.

Change it back or choose one of Google's public DNS server, for example 8.8.8.8

Found this answer here

Investigate whatever your ISP provides to turn off NXDOMAIN redirects. This has nothing to do with your computer.

You should be able to get back the regular "the address couldn't be found" text page after removing level3.com from the smart search function or completely disabling this feature:

• Open Safari > Preferences > Search

  

• Click Manage Websites…

  

• Either remove level3.com or all websites listed

• Or disable Enable Quick Website Search completely
• Restart Safari