Light Novel / Denpa Teki na Kanojo
Adorable, yes, but she'll still kick your ass. note 

Juuzawa Juu: You said you were a covert government operative, right? Then I suppose I’ll also reveal my true identity. In truth, I was a king in my previous life.
Serial Killer: Poor you! You're insane, aren’t you?
Juuzawa Juu: Everyone in this world is insane. It is because they’re insane that they don’t notice... How twisted the world really is!

Denpa Teki na Kanojo: Juuzawa Juu was just a normal delinquent teenage boy, spending his days getting into fights he would much rather avoid. One day, however, a strange girl named Ochibana Ame finds him and tells him that he was a king in his past life, and that she was his knight. She pledges fealty to him and swears to serve him as the knight she (at least believes) she once was. Originally, he wanted nothing to do with her, but when his classmate is murdered by a serial killer, he looks to her for help in solving the case.

Though it started as a Light Novel series, it has been adapted into an anime, currently at two episodes. The books and the show take place in the same world as Kure-nai.

Denpa Teki Na Kanojo provides examples of: