It seems that the problem is binding the string array values to string id value of complex object (in my case Role) - but I figured out a way around it eventually. The trick is to have this signature of the method:
[HttpPost]
public ActionResult Edit(UserViewModel user, string [] assignedRolesIds)
And then you have this in view:
@Html.ListBox("AssignedRolesIds",new MultiSelectList(Model.AvailableRoles, "Guid", "RoleName"),new { Multiple = "multiple", @class = "multi-select-list"})
With this solution, you have to reassign "assignedRolesIds" back to "AssignedRolesIds" property on UserViewModel, but that is only two lines (including check that the array is not emppty or null).