Hmmm I think your doing things fine, i'd do a
locate -u as root and then see if you get different results but from what I can see it's not installed...
Have you read the INSTALL file, i had no problems at all installing QMail as that file was really helpful
Also, when you install QMail there are sometimes a couple of patches you need to install.. They are the errno patch and the ucspi patch...
Try reinstalling it following the INSTALL