Have you looked very closely at the shots that won't align to see if there are any elements in the images that differ? I can imagine maybe Google adding watermarks or dithering or something that makes repurposing of their data more difficult.
Try overlaying parts that are supposed to match perfectly as layers and either blinking back and forth between them or setting the upper layer to Difference blending to see if there are subtle differences that you may be missing visually.
Thank you for your reply.
Well, all of the 144 screen-shots taken have the "Google Earth" and two other marks on them, but I made sure the shots overlap each other enough so that PS have room to work on them.
I made a couple attempts on the same set of shots (with marks on all of them) and most of the time photomerge tool won't have any problems with correctly alignining and blending them. There were a few instances where a row or a column, depending on how do I 'stich' the individual shots, would be correctly aligned within its row/column, but wont align with the rest of the shots.
Does it work better if you crop the images so that just map information is showing?
Photomerge looks for a perfect photographic match.