Dear Tim Maudlin,
I would like to comment on the interesting objections you raised. Let me start by the end, when you asked what reasons there could be to believe in such "strong form" of the principle. I think one reason is the following (which I ignore if it motivates Smolin, but it did motivate Peirce): in the mixed view, the stable principles that never change might be considered puzzling. One could ask the questions: What is the ontological status of those principles/laws? Why there are these laws and not others? And, irrespective of their form, why there are principles/laws at all?
Of course these questions might be answered without changing the traditional view of laws, but a legitimate possibility is to substantially change our conception of what we take laws to be. As you know this has puzzled very little physicists but has been widely discussed by philosophers, some of which have defended "deflationary" views on laws (e.g. humeans, antirealists, or those that postulate primitive causation instead of laws). Unsatisfactory as these accounts might or might not be, the point is that there are reasons to be skeptic of the traditional view of a constant set of governing laws. Then, the view that those laws also change becomes interesting to explore. At least, for those that find puzzling the traditional view on laws (and if I'm not wrong, you are not on this side).
Besides this observation, I would like to suggest a way out to your argument against the change of laws (i.e. the empirical evidence suggesting the lack of change of the actual laws of physics).
A way out would be to put forward a positive answer to the question:
Are there accounts that explain how from an underlying level guided by changing dynamical principles constant behaviour nevertheless arises?
If so, under what conditions? Of course, the conditions must not assume any sort of constant dynamical principles...
Accounts of this sort, if they exist, would help to harmonize the heraclitean view with the lack of change of the actual laws of physics.
In such a scenario, laws could be changing in a fundamental level (they should not change according to a meta-law, because therefore little would have been gained) while stable regularities would be exhibited in higher levels and codified by the actual non-changing laws of physics.
PS: I would also like to say that there is not really a problem of logical consistency due to the self-application of the principle (unlike the liar paradox). The reason is just because, under a charitable and intuitive reading, 'everything' just does not need to refer to itself (as well as it is not Smolin's intention to refer, say, to mathematical truths). Roughly stated, it refers to every thing in the world plus to the laws that describe the behaviour of every thing.