I doubt that deleting your search history would trigger a re-write of search logs. After all your history is your data, but search logs are their data. I believe it is their published policy to remove the last octet (or 80 bits, for IPv6) from client addresses in logs after 9 months and to rewrite logs without cookies after 18 months. This probably tells us more about the fact that 18-month-old search logs are not very useful for search quality than it does about privacy.

I'm pretty sure the relevant distinction is between "Data that expires after a specific period of time" and "Information retained until you remove it" in their privacy policies.

I don't see why using Brave or whatever would influence the contents of their server logs.