You're 2nd idea is the way to go, a check on logic to see if the speed is changed. Keep in mind that "negative logic" works best here. The layout is below. Refer to the Code Wizard help or *.MXT source code for the variable names and syntax. You may also need to create a variable to hold the old speed value.
%If NEWSPEED = OLDSPEED @NO_SPEED_CHANGE
CNC code output "456 TOOL CALL S3000" goes here