I've always been a fan of the Naxos Music Library. Two of the top labels for Villa-Lobos are Naxos and Marco Polo, and then there are independents like BIS, Albany Records, Chandos, and Ondine. Many public libraries (including mine) license NML for their customers, but a personal subscription is also definitely worth the money.
I also really like another, newer web service: InstantEncore. Their Villa-Lobos page is turning into an important web source, and they're constantly adding new features.
The newest feature is exciting: many upcoming concert listings at InstantEncore include a "Listen Now" feature in partnership with the Naxos Music Library. Here's an example: the Boston Symphony Chamber Players will be playing the Quinteto em forma de Choros at the Rockport Chamber Music Festival on June 28th (my birthday, as it happens). You can listen online to the NML streaming audio of the Villa-Lobos work, as well as the Poulenc and the Beethoven works in the same concert, without a subscription.
I'm looking forward to using this service in the future.