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?
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?