As Oliver C has pointed out, this is the very premise of his power.
Magnussen either has an eidetic memory, or (like Sherlock) has utilized his own version of 'a mind palace': where he can categorize and recall tiny, irrelevant details on command.
He clearly has access to incredibly sensitive information (as he is able to blackmail people), but his power lies in not being forced to make or collect hard copies of this information to still be aware of its existence. All he needs to do is convince his targets that he does possess the incriminating material.
As a black mirror to Sherlock, he is someone capable of incredible feats of logic and is so prescient of his circumstances that he keeps his knowledge locked inside his own mind. That doesn't mean to say he doesn't possess any evidence to his blackmail: it just means he doesn't have to keep the data/information stored anywhere where it could plausibly be accessed by someone else: in this case, Sherlock.
I see it as a commentary on the Leveson inquiry, on Chelsea Manning and Snowdon: huge organisations of power are brought down by their own paper-trail, and by them having to document and categorize their actions and dealings.
Magnussen, as a Murdochian newspaper magnate, deals in Gossip and Slander: he can print whatever he wants with the worst case scenario being some kind of retraction and possibly a lawsuit.
However, if what he prints is actually true, any lawsuit against him would reveal this to be so and as such he wouldn't face recrimination.
If he knows the information presented is true, and his target also knows the information is true; that's all he needs for blackmail.
If a Leveson style inquiry were to be launched against Magnussen, they'd come up with absolutely nothing because he leaves no data/paper-trail: which turned out to be the nail in the coffin for the Newspaper industry.
By not keeping the information accessible to any external sources, even subpoena's are fruitless. He's impervious to the law.