1- My understanding is that, once you get to 25k, no more Matches or Uploads. The only songs not affected by this are iTunes purchases.
2a- Yes. I actually use my downloaded Match files on several different players, not all Apple based. They are non-DRM'd AAC files.
2b- It will likely upload at its current quality (assuming MP3 or AAC). I write "likely" because there is a chance that, just because you don't see the album in your regional store doesn't mean it won't get Matched. I have a import CD rips where this has happened to me.
3- You should assume that worst and make a backup of your library before enabling Match (just in case). You can use multiple libraries, on the same computer, with iTunes Match. Some people have a main library that's not scanned in Match, and a separate library that's just for Match. This also helps you if you have more than 25k songs in your main library as you can can create than smaller second library just for Matching.
Some MP3's will not get Matched, even if the song is in iTunes - this is (unfortunately) a very common problem and there's no noticable pattern. Apple a comparing waveforms so if you have a different mastering or if your CD rip added silence to the tracks, it's possibly that this could be the reason why it uploaded.
Btw, I would add the "iCloud Status" column in your grid, if you haven't already done that. It will list what got matched and what got uploaded.
As for the MBA, you have two options -- 1) Enable iTunes Match on that computer, and you can stream the songs through iCloud. Or 2) download the songs and copy them locally to the computer. The Matched ones are 256kps non-DRM'd AAC's so they'll play on any device that supports AAC.