In this second situation, the mechanic is not universal. Remember, it isn't the strike that put him out, so it's still proper not to say, "Strike three, batter's out."
HOWEVER, some association train their umpires to call the batter out if he heads for first when he is not "eligible" to do so. This they do to avoid the issues you ended up with.
Other associations, (mine included) do not train their umpires to call the batter out because some teams, usually in the lower levels, use this as a legitimate strategy for the possibility that the catcher will make a bad throw and the other runners can advance. Under this thinking, you would be aiding the defense and taking a play away from the offense if you called the batter out.