At my last job, I shared an office with my supervisor, and his desk was
messy. I mean, my desks tend to accumulate a Cambrian layer over time, but this guy had
two desks to himself, both were covered more than a foot deep in paper. I am not exaggerating.
One day, I carefully asked him if I could help him clean up some space. I was kind of nervous, because - while otherwise the best boss I ever had - he was not very good at taking what he perceived as criticism. To my surprise, though, he broke into a mischievous grin and said, "If I start to clean up here, it will take no more than five minutes for my boss to come in here and ask me if I have nothing better to do."
His boss was kind of a neat freak when it came to his own desk, but he was indeed the kind of boss who, when he saw you cleaning up your desk, would ask you if had nothing better to do. (Which suited me fine, to be honest, my current boss is more the "You should clean up your desk"-kind of guy...)
TL;DR - a messy desk can be fine, so long as it does not control you. I have seen people whose desks looked messy, but when asked for a specific item, they could reach for it without hesitation. Once you spend more time searching for things than you save by not keeping it in order, you have a problem.