Deds has found and pin-pointed the problem.
It seems that there is a query in a function (responsible for creating the portals of a user at first log in) in api-create.tcl in new-portal/sql/postgresql that was not using the sort_key in the portals_pages table.
Because of this everytime our server executes the cron to vacuumdb the database - which is nightly, the order of the portal_pages records in the table change.
So here's how it was fixed - just go to new-portal/sql/postgresql/api-create.sql
and locate this code under portal__new function.
for v_page in select *
from portal_pages
where portal_id = p_template_id
loop
Just add "order by sort_key" after p_template_id in the query above.
This same needs to be updated in the oracle version of api-create.