1) Catalogue numbers: some labels use different cat. no.'s for CD, LP (or Cassette) versions of the same album (or single) (example: pixies: trompe le monde had three: CAD1014, for LP; CADC1014, for Cass. and CAD1014CD for CD). Which one should we pick?
CD prevails over LP, LP prevails over Tape.
2) "home" labels. Example this topic http://www.secondhandsongs.com/forum/index.php?topic=6768.0 . Am I wrong? Sometimes the two things coincide (US Artist = US Label), sometimes they don't (Nick Cave (AUS) = Mute (UK), Einstuerzende Neubauten (GER) = Mute (UK), and so on).
This is a difficult one as you say yourself. The first release is the most important, but if it's released in different countries at the same time and through different labels, we use the artist's 'home' label, but this can be interpreted in different ways (what about a band with members from different countries, like the Eagles of Death Metal?). Sometimes we just use our common sense.
3) I think I found an error! I think! As far as I know, the original (1966, UK) version of the Stones' Aftermath doesn't have Paint in Black. The american version had it. How should we handle with this kind of situation? (Bonus tracks, extra tracks, same albums with different tracklists depending on the country, and so on).
If what you say is true, Paint it Black should be put on a new medium with the American label and catnumber. All the situations you name should be settled this way (by creating a new medium with new catnumber).
If you check the Beatles page at The Beatles you'll see that "A Hard Day's Night" shows up twice: both UK and US releases.
The main reason for us to add mediums is to identify the first release of a song, which is very important for this database.
The main reason we also add label and catnumber info is to differentiate original media, re-released, etc. It's also a great way to spot date errors by checking catnumbers and their corresponding dates in a label page.
By the way, we have more extended guidelines which are about ready, and will be announced very soon. All your questions will also be explained there.
