Now when SteveC has joined Bing and they've promised to liberate their data for map creation in osm I started a new relation with the boundaries of Bing's aerial imagery covers in Brazil.
You can find the list of covered areas here: http://wiki.openstreetmap.org/wiki/Bing/Coverage/Brazil
I've already spent 4-5 hours marking the areas in and close to São Paulo, I'll definitely need some help closing up the rest. Thanks for Rodrigo Avila and Arlindo Pereira which already helped out adding RJ and RS.
I can't wait to get the clearance from Microsofts legal department to finishing of the map of São Carlos which misses quite a lot of information/traces to complete the map.