This is just a bug that I've noticed too. I punched a guy to death once in NCR, but guards killed me, and when I re-spawned and came back to NCR, I still got the message that said "You've caused troubles in this town. The guards will not protect you". So I died again and then I became unprotected.
To solve your problem, if it still occurs, try dying in a different way this time. Like, punch an NCR guard or blow yourself up. I'm not saying this will work but I have a good feeling it will.