I know the normal solution when you realize you targeted something illegally is to fully rewind the casting of the card (which involves putting it back into your hands) and depending on the REL you get a warning or just a stern don't do it again (from other forums I have been on). What I am having problems with is trying to explain it to my local store who seem to believe that they are forced to target another legal target for the spell.

They find that the announcing of the spell was legal, since only the targeting of the spell was illegal you just redo that part. When looking thru the CR I found this rule

717.1. If a player realizes that he or she can’t legally take an action after starting to do so, the entire
action is reversed and any payments already made are canceled. No abilities trigger and no effects
apply as a result of an undone action. If the action was casting a spell, the spell returns to the zone it
came from. The player may also reverse any legal mana abilities activated while making the illegal.

Then it made me wonder was is really an action. If announcing the spell is it's own action and targeting (a long with everything else that goes with casting a spell) is it's own action. As well as how entwined the targeting is with the specific action (if casting the spell is all one action). Because if casting a spell is the action then yes you could legally cast that spell, but if the action is casting the spell with a specific target then it would be impossible to do.

The problem is that term “action” is not clearly defined with CR, as I understand it.

As my understanding goes, CR 601.2h should make things a bit clearer:

601.2h. Once the steps described in 601.2a-g are completed, the spell becomes cast. Any abilities that trigger when a spell is cast or put onto the stack trigger at this time. If the spell's controller had priority before casting it, he or she gets priority.

Until all the steps in casting the spell are completed, it hasn't actually been cast - no game action has been completed to satisfaction, so if we find out it's an illegal spell in the middle of those steps we can reverse all the steps and return to just before we started.

It's possible your players may be conflating situations where mandatory triggers cause an undesirable effect on the game with casting a spell (e.g. casting Ingot Chewer when the only artifact in play is your own).

Essentially, magic is not a game of ‘gotcha’ - if the player had to initiate an action at all it should be reversible if there's something wrong.

The entire process of casting a spell - including using mana abilities when paying costs - is one action, and that entire action is reversed if the process can't be completed (insufficient mana or otherwise illegal). In addition, mana abilities used prior to announcing the spell are usually reversed, too.

Players are NEVER forced to pick a different, legal target for a spell they illegally aimed at an illegal target. That may have happened way back, in the Dark Ages - but then, a deck list problem back then was a DQ. We've come a long way, baby.

Note that, if you were to use a Chromatic Sphere or Chromatic Star before you announce the spell, we're not backing that up. However, due to a (not-so-recent!) rules change, if you use a Sphere during the casting of the spell, the card you'll draw isn't put in your hand until you finish casting - so it can be reversed. (Yes, that's all a bit esoteric, but I'm in an educational mood, I guess…)

So, when you tap all 3 of your untapped lands and announce a spell that costs 4 total, or when you tap for WGG and announce Abrupt Decay, or even when you tap 1B and aim a Terror at Baleful Strix - we will rewind all of that, including the lands you tapped right before you announced the spell.

Short version: tell your local store “Nyahh, Nyahh, I was right, you were wrong, Nyahh, Nyahh!” :)