They probably told you about their recording/reading of your e-mails and use of the internet when you first used the service - they say something like "the conditions of using this are" and buried in page 5 of the small print is their right to monitor.
I agreer that Co.s will sometimes put it in to contracts, but not always.
Entirely correct, my experience is that alot of contracts now have it in - but the legal obligation on the company is that you are notified prior to any interception - so being in the contract is not a necessity, this notification can take form of memo or email or indeed any "reasonable" notification.
Cheers