Problems searching Metadata

Luke...couple things to consider:

1. A folder is simply an item in a list/library.  Best practice is to use it for security (one level only) and NOT for organizing documents...hence metadata.
2. Metadata definitely replaces a folder structure for organization and search.

With that when you create a new view in a library, in the "Folders" section you can "Show all items without folders" view.  (See screen shot)  This will present all the documents buried in folders, without showing the folders, while honoring security settings that may be on a folder.

You'll still need to apply a filter to the view that will limit the results to under 5K.  Knowing you're library and metadata helps determine what filter to apply to limit the results.  Generally a safe piece of metadata you can use is the "Created" = [Today].  Hopefully people aren't creating 5K documents a day.