Thanks for the confirmations... and I want to agree.
That said, apparently there is indeed a "declare move" step:
You can reveal after any of the steps of a Move Action. The steps can be found on the back of the 4e rulebook, but I'll repeat them here:
1. Declare Move
2. Pay Costs
3. Leave Zone Effects
4. Walls
5. Move
6. Enter Zone Effects
Step 5: Move is when you actually change zones. As long as the enchantment is revealed before this step, then it will prevent you from changing zones.
(with respect to Force Hold being revealed)
But I agree that this doesn't necessarily change the ruling with respect to a Restrained Wildfire Imp. In effect, he could replace the entire "move action" with a "teleport action"... which instead of having a "declare move" step, it would have a "declare Teleport" step, then go on to "pay costs" (mana in this case), then do any "leave zone" effects, skip the "walls" step (since it's a Teleport), then replace the "move" step itself with a "Teleport" step, then do any "enter zone" effects (e.g. trigger traps or whatever).
Make sense?
In other words, my understanding is that the steps above are all with the "Move action" and the Imp's teleport replaces the entire "move action" with a "teleport action", and thus isn't forbidden by being Restrained (which says "cannot take Move actions").