It would appear that "yum whatprovides" is checking only installed packages, not
installed and available packages:

$ rpm -q yum
yum-3.2.16-1.fc9.noarch

$ yum clean all
Loaded plugins: downloadonly, fastestmirror, refresh-packagekit, versionlock
Cleaning up Everything
Cleaning up list of fastest mirrors

$ yum whatprovides /usr/bin/cyradm
Loaded plugins: downloadonly, fastestmirror, refresh-packagekit, versionlock
Determining fastest mirrors
 * updates-testing: mirror.umoss.org
 * livna: livna.cat.pdx.edu
 * fedora: mirror.umoss.org
 * unsigned: 
 * adobe-linux-i386: linuxdownload.adobe.com
 * updates: mirror.umoss.org
 * livna-testing: livna.cat.pdx.edu
updates-testing                                          | 2.3 kB     00:00    
primary.sqlite.bz2                                       | 507 kB     00:00     
livna                                                    | 2.1 kB     00:00    
primary.sqlite.bz2                                       | 132 kB     00:00     
fedora                                                   | 2.4 kB     00:00    
primary.sqlite.bz2                                       | 7.6 MB     00:13     
unsigned                                                 |  951 B     00:00    
primary.xml.gz                                           | 1.4 kB     00:00    
unsigned                                                       2/2
adobe-linux-i386                                         |  951 B     00:00    
primary.xml.gz                                           |  10 kB     00:00    
adobe-linux-i386                                               17/17
updates                                                  | 2.3 kB     00:00    
primary.sqlite.bz2                                       | 339 kB     00:00     
livna-testing                                            |  951 B     00:00    
primary.xml.gz                                           |  12 kB     00:00    
livna-testing                                                  74/74
Reading version lock configuration
No Matches found

$ yum install cyrus-imapd-utils
Loaded plugins: downloadonly, fastestmirror, refresh-packagekit, versionlock
Loading mirror speeds from cached hostfile
 * updates-testing: mirror.umoss.org
 * livna: livna.cat.pdx.edu
 * fedora: mirror.umoss.org
 * unsigned: 
 * adobe-linux-i386: linuxdownload.adobe.com
 * updates: mirror.umoss.org
 * livna-testing: livna.cat.pdx.edu
Reading version lock configuration
Setting up Install Process
Parsing package install arguments
Resolving Dependencies
--> Running transaction check
---> Package cyrus-imapd-utils.x86_64 0:2.3.11-1.fc9 set to be updated
--> Processing Dependency: cyrus-imapd-perl = 2.3.11-1.fc9 for package:
cyrus-imapd-utils
--> Running transaction check
---> Package cyrus-imapd-perl.x86_64 0:2.3.11-1.fc9 set to be updated
--> Finished Dependency Resolution

Dependencies Resolved

=============================================================================
 Package                 Arch       Version          Repository        Size 
=============================================================================
Installing:
 cyrus-imapd-utils       x86_64     2.3.11-1.fc9     fedora            190 k
Installing for dependencies:
 cyrus-imapd-perl        x86_64     2.3.11-1.fc9     fedora            196 k

Transaction Summary
=============================================================================
Install      2 Package(s)         
Update       0 Package(s)         
Remove       0 Package(s)         

Total download size: 386 k
Is this ok [y/N]: y
Downloading Packages:
(1/2): cyrus-imapd-utils-2.3.11-1.fc9.x86_64.rpm         | 190 kB     00:00     
(2/2): cyrus-imapd-perl-2.3.11-1.fc9.x86_64.rpm          | 196 kB     00:00     
Running rpm_check_debug
Running Transaction Test
Finished Transaction Test
Transaction Test Succeeded
Running Transaction
  Installing     : cyrus-imapd-perl                                  [1/2] 
  Installing     : cyrus-imapd-utils                                 [2/2] 

Installed: cyrus-imapd-utils.x86_64 0:2.3.11-1.fc9
Dependency Installed: cyrus-imapd-perl.x86_64 0:2.3.11-1.fc9
Complete!

$ yum whatprovides /usr/bin/cyradm
Loaded plugins: downloadonly, fastestmirror, refresh-packagekit, versionlock
Loading mirror speeds from cached hostfile
 * updates-testing: mirror.umoss.org
 * livna: livna.cat.pdx.edu
 * fedora: mirror.umoss.org
 * unsigned: 
 * adobe-linux-i386: linuxdownload.adobe.com
 * updates: mirror.umoss.org
 * livna-testing: livna.cat.pdx.edu
Reading version lock configuration
cyrus-imapd-utils.x86_64 : Cyrus IMAP server administration utilities

This behavior 1) doesn't match the man page, and 2) is a departure from
long-standing behavior, so I strongly suspect it's a bug.