I ran into the same problem when trying to get grunt to work with TFS where it would be ran by the tfsservice user. Running our builds as a different user as Christopher's answer suggests wasn't an option for us. After I added C:\Users\tfsservice\AppData\Roaming\npm to the tfsservice user's Path it was able to find the grunt-cli when I manually logged in as tfsservice, but not when the TFS Build agent performed the build. At first I just changed my build process to use the full path to the grunt.cmd file.
So I changed from using this:
grunt deploy
to using this:
"C:\Users\tfsservice\AppData\Roaming\npm\grunt.cmd" deploy
I imagine doing the same for your Team City user would also fix the problem. Of course if you do this you have to make sure that the grunt-cli is installed in the same location on all of your build servers.
Turns out though that I had just missed the final step of restarting my PC (so that the tfsservice would get restarted) and then the builds were able to find grunt without specifying the full path.
I assume that the trimmed node.js installer description shown by Zeke Lu's answer was going to say that other users need to update their Path environment variable.