I'm afraid that searching by attribute value would require fullscan over user entities and would be not very efficient if you will have huge number of users. Consider this feature apart from keycloak. How would you implement search by phone in standalone relational DB schema? I guess you would add index on this field. In this case you can add custom table to keycloak schema that will provide phone -> user mapping. See here (https://www.keycloak.org/docs/latest/server_development/#_extensions_jpa)
Considering dept attribute i would recommend to switch from attribute to groups. So you will have set of departments groups (IT,ACCOUNTING, ..) and join user to appropriate group. Then you can easily query members of desired group.
Similar approach works for roles. E.g. if you have finite numbers of values you can define them as roles and grant appropriate role to user instead of attaching this value as attribute. Querying by granted role also available right out of the box.
Note that there are available a lot of different OIDC mappers that will help you to add described mappings (no matter is this a attribute, group or role) to access token structure.