Is there a way to search for it, or do I have to scroll endlessly until i find one?

As an example, this reddit comment points to a procedure:

https://www.reddit.com/r/openstreetmap/comments/96sbd6/comme...

I tested it and it works for me.

Using:

  (area["ISO3166-1:alpha2"="my_country_code_here"];) -> .a;
    node["amenity"="telephone"].
      (area.a);
      (._;>;);
  out body;

I get 2 hits, one of which says all phones were removed in 2015.

Guess I'll continue not using Signal or Telegram.

Just move the map to your location and type "amenity=phone" in the wizard. Does that work? Are you willing to share the country you are in?

Belgium.

"amenity=phone" returns 15 matches worldwide.

"amenity:phone", "amenity:telephone" or "amenity=telephone" (no other filters) returns the same 2 matches.

EDIT:

Belgacom started removing them in 2013 in Brussels, and the rest of country followed suit. The Belgian regulator found it unnecessary to require them with the ubiquity of mobile phones.

https://www.bruxelles.be/sites/default/files/bxl/Com_.%20pre...

Ouch.

I see 740 phone booths in Berlin at least, as a counter example.