One last point that I forgot to mention about Marbury that is worth noting, lest we come away with an inaccurate understanding of the Supreme Court's power to exercise judicial review. One week after the Court handed down Marbury, it issued an opinion in Stuart v. Laird. At issue there was the Constitutionality of the Repeal Act, the statute in which the Jeffersonian Republicans had repealed the Circuit Courts Act and eliminated the sixteen court of appeals judgships (even though Article III seems to grant federal judges life tenure). The practical stakes in Stuart were much higher than they were in Marbury; sixteen federal court of appeals judgships are more important than four positions as magistrate for the District of Columbia. Moreover, Stuart did not present the Court with any nifty escape hatch akin to the one Marshall found (created?) in Marbury.
Rather predictably, then, the Court in Stuart v. Laird upheld the Repeal Act, even though Marshall surely believed that the Act was unconstitutional. He realized that a ruling that the Act was unconstitutional would have been ignored and defied by the Jefferson administration. In the face of superior power, he laid down the Court's arms.
Thus, the significance of Marbury and the real power of judicial review should not be exaggerated. At the end of the day, there are very real, practical constraints on the Court's power, regardless of its authority on paper to declare any act--legislative or executive, state or federal--unconstitutional. Marshall knew this well. He took what he could and saved the Court's prestige for fights in the future.