I just discovered this issue this morning when I searched for a bookmark that I had created on my phone last night on my ipad. The phone is on the general release 15.3.1 and the ipad is on the latest beta release of 15.4 but I don’t know if that’s relevant. iCloud system status page shows that various iCloud services had problems including Safari bookmarks but all are showing as resolved this morning. Any others seeing this?