How does Solaris find man pages

The command man -k queries against a pre-compiled database and not the manual pages themselves.

I suspect that entries may have been made in the database (see man mandb for details) for pages that don't actually exist. I am not familiar enough with the RPM mechanisms to know how this could have happened.

In a similar vein, there is considerable flexibility in what section a given manual page may claim to live. For example, on my system man Carp claims to be in section "3perl" where the underlying file is stored in .../man3/Carp.3perl.gz. The commands

man Carp
man -s 3 Carp
man -s 3perl Carp

all yield the same page while man -s 3junk Carp complains that there is no such entry.

You might find mlocate (a.k.a. locate) to be useful for hunting files by name. I presume it is available for RedHat since redacted@redhat.com is credited as the author.

It's called "paging output" or (somewhat erroneously) "pagination" …

… and man does it by invoking your preferred pager shell command, named by your PAGER environment variable, upon the output of whatever pipeline was used to generate the output form of the manual page. It falls back to a default if you haven't specified a pager command. On early Unices the default pager program, that man invokes as the default pager command with known hardwired options, was pg. On your system it is probably more or less. Some man commands look at other environment variables for pager commands, as well.

You do it by doing what man is doing: pipe the output of what you want to see into the standard input of a pager program.

You should get yourself a good book on Unix. There are a fair few that explain this, which is a very basic feature of the system. A simple Google Books search for pager unix more by me today turned up over a hundred books that discuss this. (I stopped counting at a hundred.)