OP it would help to know your location, your budget range, and can you clarify you say you want:
‘a quality horse that’s at or below 10 years of age, 4th or above with good gaits’
But then state… 'Not showing doesnt mean I don’ride through the tests. And seeing some horses doing a certain level of test does also not mean that they are confirmed at that level, as some are done badly. And yes, a lot of frustration is seeing the videos after reading the description of what level the horse is supposed to be and often they are not
"
So how is it that you will determine that the horse you become interested in is 4th or above anyway without show recordS?
You might not think much of a show record, and indeed one score in the 60s could be evidence of the pair having had a really good day on show day… but several scores in the 60s from a variety of judges does speak to a more likely proficiency at that level.
Conversely, if the pair has a couple scores in the 40s, I think one can say that the show record confirms that horse is NOT 4th level proficient, and maybe not 3rd either if there are no scores at 3rd either. 
A show record, in part, can often show us the horses progress up the training scale, and should/could reflect the appropriateness of the move up to a new level, as evidenced by the quality, consistent scores at the former level. Ie that Classical, quality training you seek.
And why 4th? If you are already riding at 4th level and ready to move up, I am surprised your trainer doesn’t have sources of horses suitable for you to consider, to cut out that whole ‘bait/switch’ you are experiencing with horses being advertised as ___ while demonstrating they clearly are not proficient at that level. Most trainers have a good network especially if they themselves still work with other trainers as most quality, UL trainers do.