Madison's main argument was that, because he hadn't delivered notice of Marbury's commission in time, his appointment wasn't valid. That being the case, the new President, Thomas Jefferson, could safely revoke Marbury's commission.

Furthermore, it's almost certain that Madison's legal counsel would've raised the issue of judicial interference in executive decisions. Before Marbury v. Madison, the Supreme Court had very limited powers; it certainly couldn't overturn decisions made by the executive.

But the Court, in a landmark case, rejected both of Madison's arguments while at the same time refusing to grant Marbury his sought-after judicial commission. They did so by invalidating an act of Congress that had given it the authority to adjudicate in such cases. In doing so, ironically, the Supreme Court gave to itself the much greater power of judicial review, the power to strike down laws as unconstitutional.