Would "works at the police" (referring to the police department) work here? If you say he works with the police, it could also be interpreted as: he is assisting the police.
Wouldn't "for" be the most appropriate?
WIllem works for the police. Willem works for the government. Willem works for the tax department.
And in that case, would "Willem werkt voor de politie" be acceptable?
I had the same answer.
Would "met de politie" have a different meaning?
Yes, that means Willem is assisting the police in some way, but is not actually a policeman himself.
What does it mean BIJ de politie? Is Willem a police officer, or is he some other kind of employee in a police station?
You can't tell by the context here.
Works with the police is unclear in English. I wrote is employed by the police. Or is he just a confidential informant? If it's your job, you wouldn't say "works with" in American English.