And guns: well, if you're pro-gun-control, this mindset (justified or not) should help you understand why the NRA is so passionately against gun registration of any kind.
In terms of the NSA: I don't think they care much for your felony record -- that is, the ones you've actually been convicted for -- they're more concerned about pre-felonies, of course. For the average citizen, though, the persistence of criminal history is going to be felt in more everyday situations, such as job searches and landlord background checks.
If I ever have a child, he or she is going to have a name like "Pat Smith", regardless of my or the mother's last name.