I was having this issue as well running iOS 16.1. I fixed it by going to “Settings > iCloud > Apps using iCloud > Show All” and toggling off Calendar and choosing to “Delete from iPhone”. After a few seconds I turned Calendar back on and allowed it to sync for a few minutes. Even before my whole calendar was synced I was able to search for events and they began to show up in the results again like normal.