We are using ST v11.4, which we upgraded from ST v8. In previous version it was working fine and yes we have set the setting exactly as you explain.
Department >> New Tickets in Portal = All Users (Login Not Required)
Maybe there is something else we are missing, as because Ticket menu is not listing at all in the portal.
In Brand >>Portal Option >> All options are enabled.
Any idea what could goes wrong with the ST upgrade from v8 to 11 which could have broken this ?