Everything is possible:-
You should be able to update 5000+ record in batches of 1000 using ExecuteMultiple:-
http://stackoverflow.com/questions/22604713/dynamics-crm-sdk-execute-multiple-requests-for-bulk-update-of-around-5000-recor
https://msdn.microsoft.com/en-us/library/jj863604.aspx?f=255&MSPPError=-2147217396
Regards Faisal