why didn't New Mexico and New Hampshire change between 2000 and 2004 then?
I think it's state choice. Maybe there is a percentage threshhold difference at which a change is triggered and neither state reached it.
Actually, NM did. It's just that it was such a minor change that it doesn't clearly show up on maps.

A few precincts in Bernalillo County, a few precincts in Cibola County...that might have been it. There were
attempts to change things more radically, but the Dem Legislature and Rep Governor (at the time) deadlocked and the NM Courts decided to change as little as possible.
The
Almanac of American Politics seems to indicate that the same happened in NH...very little change.
All states were required to draw districts based on the 2000 census data such that districts of nearly equal population were achieved. Some states had little change.
In NH, the CD's in 2000 had populations of 625,527 and 610,259. The towns of Epsom and Pittsfield in eastern Merrimack Co were shifted from CD 1 to CD 2 resulting in new populations of 617,575 and 618,211. The deviation is about 0.05%.