My suggestion is to assign the job of maintaining the signs for desks to other people.
The people who use the desk already have a lot on their minds - they can very easily forget to set the flag. Or they might have to rush out and not have the time. Or some might indeed "conveniently forget", too. At any rate, it's exctremely error prone, as you've already seen. People are fallible.
So, just have somebody whose job is to go and set signs for availability of desks either after hours or before the start of the day. If you have cleaning staff, who come in every day, then this is perfect - they (presumably) already clean the desks, and they (also presumably) come in when there is pretty much nobody in the office. So just ask the cleaning staff to put the sign needed on all desks. People coming in will remove the sign as needed. Else they risk somebody sitting on their desk if they go to the bathroom.
If you don't have everyday cleaning staff, then you can still just assign this task to somebody. Office manager, receptionist, maybe just somebody who comes in early or leaves late. It's best if they are otherwise "in charge" of something about the office, even if it's just stocking the coffee machine or something, so it's more of a natural extension to their duties. But even somebody who is just at a normal job in the office but comes in before/leaves after others can be asked to set the signs. As long as they can be trusted not to forget. Feel free to sweeten the deal with some reward, even if it's not monetary.
Also, for the visibility problem, as mentioned in another answer - flags are really good. Or otherwise something tall that will be visible when you look at the "sea of desks" as you describe it. A plaque is indeed too small to be easily spotted. You can also improvise - maybe put a hat, or a box, or a cone on top of monitors, computer, otherwise the tallest part of the desk. Something that is not annoying to see (e.g., no flashing lights) but still visible.