That's a fair point... but I do know what Tarsnap is, and it's not exactly "typical". I don't know how many non-tarsnap-using designers would come up with something which is consistent with the rest of the "tarsnap brand".
To put it another way, if you needed to roll out a new feature for Tarsnap but couldn't do it yourself, would you hire someone on contract, or do a contest for it?
Or have I misunderstood and you're saying that for $500 finding a designer than can hold that conversation is unlikely?
By holding the contest, he can get dozens of submissions. They may not be well-designed, but he can use the best theme from the designs submitted to hire a top-notch designer and polish it up, if need be.
You know what's funny? We use the word "design" for software, and you wouldn't think that you could run a contest to pick the design of a software system. But nevertheless you think someone can design his communication strategy & brand identity by a contest, without spending the time to write down the requirements first.
To the OP: my advice is, just don't bother with a contest or a logo. Find someone (a friend) who is good at typography, and ask him to typeset the word "Tarsnap" for you in a way that looks good on that banner. Just use that as a logo, until you have the time & resources to hire someone to do a proper brand identity for you (because that's what you are asking for here, not just a logo)
Then you call in a real designer to look over the submissions and pick the one that inspires them, and do an improved version of that.
By opening a contest, you're not only going to get a much lower quality of submissions, but in the end, the final decision is going to be made by you, someone "useless at anything artistic".
Paying a designer $500 won't get you a full brand identity makeover, but that's not what you're going for. You should be able to find a talented designer who will spend an hour discussing what you want to get our of your logo, some time going over a number of their own ideas, and then wrap up the project and give you the sizes you need and a vector file if you ever need to scale your logo up or down.