Okay, maybe the better way to say it: It's not prosecuted. There are a few peculiarities in German law using this construction: It IS illegal, but you don't gain anything by prosecuting. So it's written explicitly in law that it cannot be prosecuted unless certain conditions are met.
For the "wasting police time": the term used in German law translates to "obstructing justice", but there are a lot of exceptions whether or not a willful lie can be prosecuted. Say, lying about the whereabouts of a perp (though there are graduations depending on the severity of the crime). See, German law recognizes that perps do not want to be caught, and most people cannot be forced to help police doing that. As an example, if you state "I don't know where he is", even though you do, this lie cannot be prosecuted. However, stating "He's in Berlin" when you know he's in Cologne at the other end of the country, it can, because that's sending police on a wild goose chase. (You can still send police to search in Berlin if you construct the lie carefully, and offers it as a possibility instead of an absolute fact, and get way with it). There's still the problem of proving that you know about Cologne, and proving that you state it intentionally to mislead police, which is why it's mostly considered a waste of time to prosecute.
