i push the code, i made changes in the sql search and if you have a lots of revision you can select SQL option, normally the draft always will be include in the first search (if the image belongs to this post/page draft | has been upload for this post/page)
I made a test, i put 500 quantity and the query was fast, it was my browser who had the problem of render all the information. (i have 500 post and 1000 image in my site, so is not like your site, but i hope this will help you with the search time)
And for the paid plugin, is only one idea, i have to search time to do it, and i dont know if will sell, so for the moment is only in my head