If memory serves 56K was pretty widespread in _availability_ by 1998. I worked at a small local ISP in San Diego from 95ish to 97ish and they were available at the tail end of my time there.
You're right that it was rare to get full 56Kbps especially on the early modems and especially on the dreaded winmodems (https://en.wikipedia.org/wiki/Softmodem).
All that said, I also seem to recall that at least in major cities 56Kbps never really went anywhere as cable modems started becoming widely available.