I am having a similar problem, no e-mail notifications.
Extract from my CallHistoryService.log
16:22:53.370|Inf(03)| VMMonitor: Scan VMBox:'10'
16:22:53.370|Inf(03)| VMMonitor: File vmail_07768123456_10_20110721152253 added
16:22:53.372|Inf(03)| Number of VoiceMails directories:2...