The default and lowest standard of review for constitutional questions in the US is "rational basis review". Higher standards are required, if fundamental rights or suspect classifications are at issue. As Cornell summarizes the situation, "to pass rational basis review, the challenged law must be rationally related to a legitimate government interest". Assuming a law which is not subject to higher review, it could fail rational basis review if the identified government interest is not legitimate (the cases of interest here), or if the interest is legitimate but the law is not rationally related to that interest.
An example of upholding a "legitimate government interest" is Christian Legal Society Chapter v. Martinez, where a UC anti-discrimination requirement was objected to on First Amendment grounds, and the court rejected that argument, finding that "The all-comers policy is a reasonable, viewpoint-neutral condition on access to the RSO forum; it therefore does not transgress First Amendment limitations" – the court found the university's policy to be rational, indeed "creditworthy".
My question is, has any ostensive government interest ever been found by a court to be illegitimate? The test would be a case not involving triggers for higher review, where the law was overturned, and the failure was because the interest was deemed to be illegitimate (not because the law isn't rationally related to the interest).
I specifically want to exclude any cases where the matter does involve suspect classifications or fundamental rights, but where the court employs a rhetorical flourish and says "This wouldn't even pass rational review", or otherwise declines to focus primarily on existing triggers of higher-level review. An example of a kind of case that doesn't clarify the matter is St. Joseph Abbey v. Castille, 712 F.3d 215. Although the court concludes "The funeral directors have offered no rational basis for their challenged rule and, try as we are required to do, we can suppose none", the ruling also starts by saying
The district court enjoined their enforcement, finding that they deny equal protection and due process of law. We will AFFIRM the judgment of the district court.
They do not say that the interest is illegitimate. (My underlying hypothesis is that there are no cases of low-review where a government interest is held to be illegitimate, implying that all government interests are legitimate).
The case of US v. Morrison adds a complication to the question. In that case (cited in this answer), a law granting federal civil remedy to victims of gender-motivated violence was struck down. The original belief of Congress was that the law would be allowed under the Commerce Clause and the 14th Amendment. The court in its opinion set forth a fundamental constitutional limit on what the federal government can do:
Every law enacted by Congress must be based on one or more of its powers enumerated in the Constitution. “The powers of the legislature are defined and limited; and that those limits may not be mistaken or forgotten, the constitution is written.” Marbury v. Madison
The court did not go any further in pointing to a specific clause in the Constitution (e.g. the 10th Amendment). Likewise in Marbury v. Madison, the constitutional limit on government is captured in the statement
The distinction between a government with limited and unlimited powers is abolished if those limits do not confine the persons on whom they are imposed, and if acts prohibited and acts allowed are of equal obligation. It is a proposition too plain to be contested that the Constitution controls any legislative act repugnant to it, or that the Legislature may alter the Constitution by an ordinary act.
The Morrison court then rejected the claim that there is such constitutional authority. This puts the case into the "strict scrutiny" basket. Similarly, in US v. Lopez, an anti-gun law (ostensively authorized by the Commerce Clause) was overturned because "The Act exceeds Congress' Commerce Clause authority", and accepting the government's position "would bid fair to convert congressional Commerce Clause authority to a general police power of the sort held only by the States" – a 10th Amendment issue.
The complication then is that a court has available a tool for upping the level of scrutiny, if it can be found that there is no constitutional authority for a particular law. The concept of "legitimate interest" could then be dispensed with entirely (although it certainly does exist in the case law, in the affirmative but apparently not in the negative).
An observed in Wes Sayeed's answer, one prong of rational basis analysis is whether a law exceeds authority, and a lesser question (the one I focus on) is
Whether or not there is an articulatable need for the law to exist (the Congress/Legislature does not have to justify its reasons for a law but it usually does, and that reason is presumed valid regardless of how it's contrived).
I am looking for evidence that this lesser prong actually exists, and distinguishes possible vs. impossible laws. Or, is every case of "not a legitimate government interest" elevated to the status "not a constitutionally-granted power"? Even more briefly, is "legitimate interest" just another way of saying "constitutional power"? J. Stevens concurring in NY Bd. of Elections v. Lopez Torres states that
as I recall my esteemed former colleague, Thurgood Marshall, remarking on numerous occasions: “The Constitution does not prohibit legislatures from enacting stupid laws.”
I have not located a relevant majority opinion which upholds this conclusion.