I have tried to do what has been suggested in this forum, but when I go press "Change" for my email accounts,
Where are you pressing Change? POP3 accounts have a setting to delete mail from server after 14 days. That is in File, Account Settings, double click on the account, then More Settings, Advanced. But it is not available if you are using IMAP. Your symptoms do seem to indicate that a POP3 account could be responsible.
I know some phones will delete appointments from outlook as they age off the device - it's possible they could do the same with an email account. But if it worked before an nothing changed on the phone, and you had to reconfigure everything on the computer, it points to the computer as the problem.