Have you tried the Contractors list on Gamasutra?

http://gamasutra.com/contractors/contractor_display.php

By the way, I moved this to the Production/Management board.

Oh, and I assume you've tried our Classifieds section too.

it feels like half of the work is tracking art studios and individual artists to evaluate. Then follows an extended period where you try to make sure that the person/company is reliable and actually has the skills / experience to do what you want.

Yes. Welcome to the producer's world. People seem to think producers don't actually do anything. A lot of it is, as you say, finding and vetting the talent. Once you make a list of likely candidates, you can check on the candidate's work - see what games the person or company has worked on, and then get the name of the producer they worked for, and ask questions. Did the candidate deliver on time, on spec, on budget? How were they to work with?

is there somewhere a list of reliable/recommended art studios to work with?

Not that I know of. Recommendations also depend on the project.
One studio might be a good fit for one client, but bad for another :\ It's hard to be objective when every project/team is different.

Right now, it feels like half of the work is tracking art studios and individual artists to evaluate. Then follows an extended period where you try to make sure that the person/company is reliable and actually has the skills / experience to do what you want.
Most of the work we get is organic word of mouth, people we know from previous relationships, or people we've met at networking events, like conferences.

Yep... We do art outsourcing, and basically the reason that we charge more than a lot of other people is that we always put an art director / producer on the job, as a filter between the team of artists and the client. That director will review all the work and get artists to redo things before the client even gets to see it. The result is that the client gets exactly what they've asked for, but yep, the cost is that the client has to pay the extra overhead of this management layer too.
If you're hiring individual contractors yourself, then you're talking on that role of art director / producer, which will almost be a full time job for you.

As a very small indie company we still need AAA quality art, but it's actually rather hard to track down art studios. Pointers, links etc are all very appreciated.

Lots of AAA games outsource some art too -- you can try and find out what studios they're using :wink:
I hope you're comfortable with the fact that AAA quality art is expensive though, and that indie budgets and AAA quality are a fragile mix, which usually requires AAA-quality artists to be working with you closely for something other than the money they deserve (e.g. equity in the company...)