Searching relies on index tasks running in the background to update changes made on the database. As standard the index for quick/standard search runs every hour and for power/advanced searches it runs once a day.
On-premise customers can check the indexes are running by a system admin user going to the scheduler task list and checking the Index: update quick search and Index: update all tasks.
To check this:
Click System admin menu and then click Server maintenance.
Then select Scheduler task list.
For cloud customers the Profile support team can check on Index tasks if a new online support case is raised.