Well thats solved it! Not sure if you saw my second edit of my post before you submitted yours. I changed around a few parameters that logicall would make more sense as 'department' should go first as it contains many 'categories' so I had to them reorder the parameters 1, 2, and 3. But of course that didnt work.
To be honest I was a little puzzled by your code "categories.CategoryLink = ? OR -1 = ?" I didnt think you could put -1 for the URL parameters markup.