Actually in the case of Columbine if I recall details correctly Eric Harris (who was arguably the force behind it, Klebold was just a follower) was on an antidepressant medication but quit prior to the attacks after he was turned down by the United States Marine Corps.

Linking criminal records to mental health records would probably be the best move that could come out of all this, since to the best of my knowledge criminal records currently do not contain mental health information if the person has a clean record, but I can see where the complaints with this would come in the form of people saying that by linking the two it would be considering people with mental health as criminals without them ever committing a crime.