Installed the WC Fix Attributes plugin Version 1.0 | By Tofandel as found here:
Works a charm and really speeds up searching existing attributes 10 fold with Custom Attributes having 1000+ options available.
However, a small issue I have run into is if a new custom attribute is added, this new attribute cannot then be found for the next 20-30 minutes, when they do eventually seem to populate. Anybody else using this plugin found this and worked out a workaround for how quickly it populates the search results.
Of course, without the plugin, the search takes 15-25 seconds to show results but when you 'Add New' they are available instantly.