To add to this story, now that I and my colleague have looked into this a little more.
If I use 'Daniel' as my search term, I find contacts, notes, opportunities, quotes, orders, invoices, accounts and marketing list items contain this term
If I use 'Stephen' I only get accounts, despite contacts showing up 'live' as I type in the search box.
My colleague, with the same Admin permissions as me, does not have the same issue - all results from all entities show up for all searches
I have tried the same search using a different browser (Chrome, I was originally using Edge) and on a completely different PC on which I had never accessed Dynamics before, and I still get the same outcome.
We have tried to find any settings that may be different, but with no luck.
Has anyone seen this before? Any ideas as to what we could try next?
Many thanks