I work at/in the sales department?
"At" sounds completely wrong.
I think it's "in" because "department" is grouping of persons. You're working "in" the group.
"For" would also be correct but have a slightly different meaning. You could say, "I work for the sales department." This would be more an emphasis of you as an individual and maybe present ambiguity of how well you fit in or suggest a briefer or more transitory period of time to be working in sales.
Often, we'll simply say, "I work in sales." This can mean the sales department with "department" silently implied and understood. It can also mean "I work in sales [as a chosen profession]."
What naturally sounds right after "I work at..." is a company name. For instance, "I work at Apple."
Together, they could be combined such as, "I work in sales at Apple."
I have heard both but in the sales department is way more common.