1. Implementation (sites do not need to have a sitemap; or those that have it, may not have an accurate one)
2. Discoverability (finding sites in the first place, you'll need a centralised directory of all sites; or resort back to crawling in which case sitemaps are not needed)
3. Ranking (biggest problem in creating a search engine)
1. This would be up to sites, to your point, major question would be best way to create incentives.
2. This is solvable via a number of approaches, but the search engines themselves would be mostly responsible for finding the right approach for their business. I know how I would do it.
3. Indeed, which would be the main point of this decentralization, to let search engines focus on their hardest problem.
Edit: would Kagi not benefit from having to worry about crawling / indexing sites?
It would, but sitemaps do not provide that function as we discussed above. However if EU Open Web Search succeeded, that is something we could probably use to some extent.