Ok, I wondered about that but assumed that I would at least need to use the multi-insert behavior. I did as you mentioned and it works perfectly using just the single insert behavior.
For anyone else looking for this solution, I added a second Single Insert behavior to insert into a table that acts as the relationship between the department categories table and the products table. I have 3 tables here.
tblProducts (first insert adds the new product to this table)
tblDepartmentCategories (this table holds the department categories and is used populate the multi-select list)
relDepartment_Products (second insert adds all of the selected department's ids and the product id into this table)
In the second insert, I bound the product id column to the session created by the first insert behavior. I then bound the department id’s column to the multi-select. I assume you would have to manually add  to the name of the multi-select like this, name="DepartmentCategory".
If I have anything wrong here, please let me know.
So, having that one finished, I am now working on the update page for this same record. I’m not sure yet if I will see the same issues since I will need to use the MRT behavior, but I will report back.