I've had the same problem too. Removing / re-adding will partially solve the problem. You will still continue to receive mail but downside is, you will get the error everytime it does a "pull". Frustrating indeed.
Update: After fiddling around with it some more, I realize that this could be a problem with the OS caching. Prior to this, I had a problem with the phone locking up. I tried to retrieve new emails by manually tapping sync and got the error stating that last updated was 4 hours ago, with the error code 80070018. I wasn't getting any emails then. I switched off the phone, but it wouldn't turn on when I tried. So I did a soft reset (volume down + power), and once it booted up, everything was running, except for this email account that I had problem with. I then proceeded to remove and re-add the account. Now mails do come in, only problem is, it still shows the last updated 4 hours ago error message with error code 80070018.
Man, I've never had such a problem on my Lumia 800. What a fail it is for Microsoft, yet again.