> The issue is that they, and other administrative organs, often change their interpretation of what the law "has always meant".
Yes, and if that conflicts with what the courts believe the law has always meant, those decisions won't survive contact with the legal system. An ex post facto law is a law creating (or enhancing) criminal penalties for acts that exist before the law is passed. Changing administration interpretations are like changing prosecutorial priorities (and the former comes with a lot more notice and specificity than the latter) -- they only have effect so long as they are within the bounds of what the courts will accept was covered by the law when it was passed.