Dear small indies with a low art budget,

When we approach you for an art job you've put up, we do not want the "opportunity to shape your free RPG game" or "design the characters however we want" or "have input into the workings of the game" in exchange for a small budget. Maybe that is a good opportunity for a hobby artist who you can't 100% count on to stick around, but for an artist used to doing work for money?

That is called work. Work that you are calling a "favor to us". Adding design work to a project is not a favor. It will in fact take us more time to think of what to put in your game and THEN draw it than to just get a list of art from you. Some people would like to draw what they want for other people, but most artists already draw what they want! Our ideas are for our own games and they took a long time to think of and design in a coherent way. We don't want to "just draw anything" when we are taking on paid work. We charge a design fee when people make us do the design work because designs take time. If you would like to pay the design fee, we will gladly design things for you, but for a lot of artists? The design takes more time than the execution. Our sketch artist can pump something out in 20 minutes with a good description. Any part that she has to think about takes longer than that.

A small budget? We can work with. But don't offer us a chance to design your game for you (read: more work) in exchange for less money.

Instead, if you know you have a small budget and want to entice your artist to continue working for you, have a clear cut design for your game already worked out and a list of assets you will need. Be willing to compromise on how some pieces will be done, and don't ask the artist for more than 2 miniscule edits without expecting to pay extra. Allow the artist to retain most of the ownership of all their work. Those are things that artists value; things that will lower the time they have to take on your project, so they can still make a decent hourly even on a small budget. Adding to the work they're doing and then also paying less? Not so much.

[Edited to make something clearer.]

I've offered just that, and still have had poor results. I've come to believe it's luck, money or nothing, until I'm proven wrong.

Well, if your money is still too low for what you want, then unfortunately, yeah. This is not for people who have no budget, more for people who have extremely low-but-still-potentially-feasible-with-corner-cutting budgets. For example, you can probably, if you do a bit of digging, complete a pixel art game on $1000 if you just need an artist and actually want it to look good. But, that price will never go for any 3-D game. I try to always make suggestions to people to lower their costs, but even with lowering your costs, there's a limit to how little someone will accept for their work.

Ah, I see. No, it's not "in exchange" as in "you don't pay and you get art free". It was "you have a small budget, therefore you should understand that you are paying a low cost and limit your demands as mentioned above." Sorry, but even "messy" art that looks good takes talent. No game maker should go into a game expecting to pay nothing for the art unless they are drawing it personally. =/ Heck, my group does art and we still have to hire artists to fill in the blanks.

Edit: In addition, I mentioned later that you want to lower the time the artist takes so they can still make a decent hourly wage even on a small budget.

If you have 56K yearly, I'm not sure why you're on here and not on any of the hardcore professional freelance sites. Perhaps that's your problem!

So what pointers would you give us indie developers with small budgets? From what I've been able to discern, a lot of freelance artists are either priced way out of an indie budget or way too restrictive. For example,

I have an art budget of about $1000. I need some decent art for a 2D browser based game. No sprites, no texures, no meshes. Just roughly 100 icons (32x32) and 35ish concept art for backgrounds (mostly OC, but a few landscapes). I've looked on DA for prices, and its looking like it will cost me a minimum of $3000 if I don't want it looking like a 12 year old drew it. Plus, most of the freelancers I have seen also say that 1. "I still hold legal rights to the art." and 2. "I reserve the rights to the artwork and you may not make money from it." (Copied from actual DA posts). From what it sounds like, in order to have quality work done AND retaining the full rights to that work would be considerably more expensive.
So what would you suggest?

Of course its them being smart. The most financially profitable thing George Lucas did with the first Star Wars was retain full rights of the Star Wars franchise. So in the G.Lucas vs. Fox equation, I would rather be on the G. Lucas side of things. And while chances of an indie game exploding like Star Wars is pretty rare, I would rather be protected in the event it does so my IP doesn't get pasted on a million coffee mugs for someone else to profit from. Plus, this closes off a lot of potential for the developer as well. For example, if the game is doing moderately successful and some larger company offers to buy it, we legally cannot sell them the art resources since we do not own them.

Which kind of leads back to the OP's original statement. Since it sounds like the norm for freelance artists to retain the rights to exploit art bought and paid for by the developer, maybe developers are looking for a bit more vested effort into the project. From a business standpoint you have two main factors: The Worth of the Art and the Worth of the Code. Are they equal? Is one worth more than the other? How many successful games would still be successful if they had a different, but just as talented, artist/programmer? I feel that most games are played and purchased due to the game (code) and not the visuals. Dwarf Fortress is played by a surprising amount of people, despite having no graphics. And I think Angry Birds would be just as popular if they had a different artistic rendering of the birds.
Of course, we all want good art for our projects. We just don't want to be like Fox and kick ourselves later.