Mail store service is not listed in the Blackberry services which I think explains the lack of email sync between the BES and devices.
This service is not as important as it sounds. It more or less downloads the GAL to BES and enables you to search for new users when you create them in BAS. Mail flow should work without it.
I guess you have other issues that will not be solved by installing this service. Check the MAGT log for errors.
Anyway, of course, the Mail Store Service should be there. Maybe you can install it by the command line "BlackberryMailStorerSrvr.exe -install".
Or you have to re-install BES.