Marbury v. Madison is much more nuanced than that.
Imagine that the decision in Marbury v. Madison came out the opposite way; or, more abstractly, that the Supreme Court upheld legislation that was prima facie contradictory to the text of Constitution. That would necessarily imply one of two things; either 1) the courts are choosing to enforce an illegal law, or 2) the courts are deferring to Congress's interpretation of the Constitution and thus concluding that, despite appearances, it's legal. The former would mean that there was no rule of law. The latter would mean that the Supreme Court isn't actually the _supreme_ court, but rather an inferior court in terms of interpreting the law.
The logic of Marbury v. Madison says that because the American form of government is built upon on the principle of separation of powers, and that in the English tradition it's the court's role to interpret statutes (not the legislature's), that it would be a violation of separation of powers for the Supreme Court to defer to Congress's interpretation of the constitution. Also, in the English tradition of Due Process laws can generally only be enforced through court order, not independently by executive fiat. And the U.S. Constitution explicitly says that the "judicial power" rests with the courts.
The academic debate about judicial review is misleading. Judicial review is often described in contradistinction to the rule in England--Parliamentary Supremacy. But we must remember two critical things: 1) the UK does not have a written constitution, and 2) until just a few years ago the highest court in the UK was composed of Law Lords from the House of Lords. The House of Lords being a constituent part of Parliament, the highest court was thus the same institution as the body writing legislation.
The debate about what we now call judicial review didn't just occur at the national level; it played out in every single state. And while many contemporary jurists paid lip service to the idea of courts being inferior to the legislative body, I don't think the debate played out any differently in any of original colonies or subsequent states in actuality. It's really difficult in the Anglo-American legal tradition for courts to _not_ have the power of judicial review, while maintaining the logic the political system is built upon.
We can _imagine_ a constitutional system where courts defer to the explicit or implicit decision of the legislature regarding constitutionality. But I don't think that actually exists anywhere in the world where the principle of separation of powers is enshrined in the organic law (written or unwritten). The closest I can think of is Japan where their supreme court regularly seems to uphold statutes which conflict with the written constitution, but they _have_ nullified statutes a few times, and certainly I don't think they've formally abdicated their role wrt judicial review.
We do have a form of the above in the United States. There are some situations which are considered "non-judiciable" by the Supreme Court. For example, nobody can challenge through the courts some of the formal requirements the Constitution imposes on Congress regarding their proceedings. The Supreme Court has said that in some situations it must refrain from exercising it's normal power of judicial review because it would cause the court, as an institution, to become too entangled with another branch of government. This is also partly why courts are reticent to censure or make demands on high-level executive officials, e.g. regarding national security. Even if behavior is patently illegal, by getting involved the court risks injuring the very principle of separation of powers by imposing its interpretation of the law above that of the other body.