Thank you for you reply, I guess you were close.
I found out clicking around, still not easy to find (just started with Joomla, I have a hard time...)
What was it?
I had a better look at the menu item that links to the category in which the items were not ordered as expected, and it turned out things were explicitly set to alphabetical order (and also the list limit was set to 5, that also gives nasty behavior).
So for future use/reference: look in "List layouts" of the menu item (setting items back to "Use Configuration Settings" did the trick)