i still think Pia's idea stands
Try poking around in the tools/options menu. Maybe something got changed vis a vis the deleted items properties.
outlook has this setting to archive or delete any emails older than a couple of days!