It's not hard, it's hard to maintain. It's up to the DEV to update their plugins with version compatibility. Some do, some don't.
Just add an icon next to it for those that have been "tested in current version" or tested in your version or something and allow to filter by that option.
There IS a 'tested up to...' on the side bar in the plugin menu AND if you try to install it via the WP admin plugins page, you get notified if it's NOT listed as tested.
Yes, the search sucks, but since you're going to want to read the plugin page anyway, it's not a great deal of loss. Yet. It is annoying, but not a 'critical blocker' :)