I think this is already implemented. The current test case creates the following users:
Miss Marple (Department: Kennel)
User Profile Plugin (UPP) is installed.
Searching for "ken*" produces 4 results:
Miss Marple (because of the deparment and UPP is installed).
Please comment on this issue, if you think this is not how it should be implemented.