I have noticed that quite often the first track of an album which is already marked as track "1" will fail in the MB lookup but the rest of the tracks proceed fine. It happens enough that it makes me suspect there might be a small bug where this happens under very limited circumstances.
Is anyone else seeing this kind of behavior? Or is it purely my imagination?
I haven't noticed this, but maybe you could experiment. If you are saying the first track is already marked as track 1 and all the others have no track then if the track number is actually wrong it is going to be more difficult to get a match because the track number field is not going to match. Next time try resetting the value and blanking the track number to see if that effects results or run Manual Tag From MusicBrainz which will show all possible matches including ones where the score was too low for the Automatic match to pick it.