User Directory search does not return user from public room with limit parameter

This issue has been migrated from [#16472](https://github.com/matrix-org/synapse/issues/16472).

---

### Description

`/_matrix/client/v3/user_directory/search` with a limit does not return users that are in a public room and I don't share a room with

### Steps to reproduce

- Create some users
- Let one of the users join a public room
- Query a user from the public room with another user, that does not share a room with the other users
- Be sure the in addition to the query term there is also a limit of 50 set

Expected:
Other user with no shared room, but in a public room should be returned

[spec](https://spec.matrix.org/v1.8/client-server-api/#post_matrixclientv3user_directorysearch) „the homeserver MUST at a minimum consider the users the requesting user shares a room with and those who reside in public rooms“

What happens:
Directory search does not return the user


### Homeserver

localhost

### Synapse Version

d6b7d49a61ca4c6f87d93ff9eb6a9fa6faef443c

### Installation Method

Docker (matrixdotorg/synapse)

### Database

SQLite

### Workers

Single process

### Platform

- Podman locally
- Docker for Element Web CI

### Configuration

_No response_

### Relevant log output

```shell
2023-10-12 11:22:10,546 - synapse.access.http.8008 - 465 - INFO - POST-159 - ::ffff:10.0.2.100 - 8008 - {@user_3:localhost} Processed request: 0.001sec/0.000sec (0.000sec, 0.000sec) (0.000sec/0.001sec/1) 30B 200 "POST /_matrix/client/v3/user_directory/search HTTP/1.1" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Cypress/12.17.3 Chrome/106.0.5249.51 Electron/21.0.0 Safari/537.36" [0 dbevts]
2023-10-12 11:22:11,293 - synapse.access.http.8008 - 420 - DEBUG - POST-160 - ::ffff:10.0.2.100 - 8008 - Received request: POST /_matrix/client/v3/user_directory/search
2023-10-12 11:22:11,294 - synapse.storage.txn - 742 - DEBUG - POST-160 - [TXN START] {search_user_dir-59a}
2023-10-12 11:22:11,294 - synapse.storage.SQL - 453 - DEBUG - POST-160 - [SQL] {search_user_dir-59a} SELECT d.user_id AS user_id, display_name, avatar_url FROM user_directory_search as t INNER JOIN user_directory AS d USING (user_id) LEFT JOIN users AS u ON t.user_id = u.name WHERE ( EXISTS (select 1 from users_in_public_rooms WHERE user_id = t.user_id) OR EXISTS ( SELECT 1 FROM users_who_share_private_rooms WHERE user_id = ? AND other_user_id = t.user_id ) ) AND (u.locked IS NULL OR u.locked = FALSE) AND value MATCH ? ORDER BY rank(matchinfo(user_directory_search)) DESC, display_name IS NULL, avatar_url IS NULL LIMIT ?
2023-10-12 11:22:11,294 - synapse.storage.SQL - 458 - DEBUG - POST-160 - [SQL values] {search_user_dir-59a} ('@user_3:localhost', '(bytebot* OR bytebot)', 51)
2023-10-12 11:22:11,294 - synapse.storage.SQL - 479 - DEBUG - POST-160 - [SQL time] {search_user_dir-59a} 0.000075 sec
2023-10-12 11:22:11,294 - synapse.storage.txn - 846 - DEBUG - POST-160 - [TXN END] {search_user_dir-59a} 0.000268 sec
2023-10-12 11:22:11,295 - synapse.access.http.8008 - 465 - INFO - POST-160 - ::ffff:10.0.2.100 - 8008 - {@user_3:localhost} Processed request: 0.001sec/0.000sec (0.001sec, 0.000sec) (0.000sec/0.000sec/1) 30B 200 "POST /_matrix/client/v3/user_directory/search HTTP/1.1" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Cypress/12.17.3 Chrome/106.0.5249.51 Electron/21.0.0 Safari/537.36" [0 dbevts]
```

### Anything else that would be useful to know?

Found with one of the [Element Web end-to-end tests flaking](https://github.com/vector-im/element-web/issues/26138). With the test this occurs quite often.