This is because target legality for the spell is checked once when putting it on the stack (usually when casting or activating it) and once when it would resolve. Correct?
Yes.
601.2. To cast a spell is to take it from where it is (usually the hand), put it on the stack, and pay its costs, so that it will eventually resolve and have its effect. Casting a spell includes proposal of the spell (rules 601.2a–d) and determination and payment of costs (rules 601.2f–h). To cast a spell, a player follows the steps listed below, in order. A player must be legally allowed to cast the spell to begin this process (see rule 601.3). If a player is unable to comply with the requirements of a step listed below while performing that step, the casting of the spell is illegal ; the game returns to the moment before the casting of that spell was proposed (see rule 725, “Handling Illegal Actions”).
601.2c The player announces their choice of an appropriate object or player for each target the spell requires.
(similar rules exist for activating abilities) and later:
- Resolving Spells and Abilities
608.2b If the spell or ability specifies targets, it checks whether the targets are still legal. A target that’s no longer in the zone it was in when it was targeted is illegal. Other changes to the game state may cause a target to no longer be legal; for example, its characteristics may have changed or an effect may have changed the text of the spell. If the source of an ability has left the zone it was in, its last known information is used during this process. If all its targets, for every instance of the word “target,” are now illegal, the spell or ability doesn’t resolve. It’s removed from the stack and, if it’s a spell, put into its owner’s graveyard. Otherwise, the spell or ability will resolve normally.
Then why does the same not work for a spell that cares about power or toughness
That spell works exactly the same way. You can definitely make the creature an illegal target by decreasing its power below 4 (see the emphasis above). However, Giant Growth won't help, since it increases power; you'll need something like Ovinize instead.