If they considered this merely a hiding problem then to never ever have considered whether it might be possible to hide from them after all, or to not have considered a legendary item of hiding in that context would be pretty incompetent.

My impression was that it was legendary in the sense of "yeah, we tell those stories to our children" instead of "look, every student's sat under the Sorting Hat, it exists and there are thousands of witnesses." That's an unfortunate part of magical stories- it's hard to avoid the Every Rumor Is Completely Correct trope without inundating the reader with worthless information, and so when you say something is legendary it's not clear whether you mean it's +6 or it probably doesn't exist.