Hi,
The random results in this case is selected from the database via randomized ordering (as that is the fastest reliable method), so it unfortunately affects the order of the results. As an alternative you could do a search for an empty phrase: https://i.imgur.com/QYF3YkQ.png
The results will not be selected at random however.
With the taxonomy issue, can you please check if this option is disabled: https://i.imgur.com/FHfouEt.png
When enabled (by default), the plugin will display items that are not associated with any of the taxonomy terms.
