It is difficult to search for users (in code) based on profile information in Drupal 6 due to the flexible nature in which the profiles module stores information.
Basically profiles are stored in 2 tables.
mysql> select * from profile_fields; +-----+------------+-------------------+-------------+---------------------+------+-----------+--------+----------+----------+------------+--------------+---------+ | fid | title | name | explanation | category | page | type | weight | required | register | visibility | autocomplete | options |



