Follow the steps below to address the problem around People Search returning no results (even though you know that there are people in the database that match your search criteria):
1) Open Shared Services Administration
2) Click on Search Settings > Content Sources and crawl schedules > Manage Content Sources
3) Select the "Local Office SharePoint Server sites" content source
4) On the "Edit Content Source" screen, Update the Textbox for "Start Addresses" to include a new entry for the URL of your site collection name starting with "sps3://". For example, "sps3://intranet:80"
5) Select the checkbox "Start full crawl of this content source" and Click "Ok"
6) Wait till the indexing finishes. (You can check the status of indexing by accessing this area - "Shared Services Administration: SharedServices > Search Settings > Configure Search Settings"
7) Goto your site collection (for example http://intranet:80) and perform your people search to find results