Hi ariady,
Can you confirm if you're using SQL Server for the SEPM database (as you've got 4K+ clients I highly suspect you in matter of performance), if so the SQL Server version. I suspect you might encounter a defec that started to occur a while ago for SEPM 11.X when using SQL server.
Not entirely sure as logs would help to confirm it. Keep this article in mind just in case. It was mentioned October but since that date, definitions started to get a little bit bigger than usual for 11.X so maybe you need to do the modifications of the files mentioned on the KB below (some customers faced that issue later than october).
=> http://www.symantec.com/business/support/index?page=content&id=TECH211503
Otherwise, do not hesitate to post here the Log.LiveUpdate and SesmLu.Log so we could provide you a proper work around/solution.
Kind regards,
A. Wesker