That always works for me. I've even written a batch file that I can run from a new console to set that up (mine was installed with Dev-C++, so the path is different from yours):
Now, I have to do that every time I open a new console (AKA "Cmd Prompt"), because every new shell and sub-shell has its own environment which is a copy of its parent's environment. So my question to you is whether you had added that directory to the path in one "Command Prompt", which you subsequently closed, and then tried to run gcc in another one. If that is what you did, then your change to PATH did not affect the parent's environment and it ceased to exist as soon as you closed that console.
You should either create a batch file like mine that you can run each time, or find change the system environment's PATH variable. If you do the latter, then you will need to discover where your particular version of Windows has chosen to hide that dialog from you. Good luck with that and happy hunting!