Out of desperation, I simply factory reset my iPhone, and did NOT restore it. I manually went in, and set up all my accounts, added my Apple ID, re-installed apps, and treated the device as a new one entirely. It took me well over an two hours just to get emails, contacts and calendars back.
But after close to two weeks, email is back to normal, and iTunes even stopped duplicating playlists. My wife, who got a brand new phone and migrated her data, has the problem. My antique phone is fine.
I think the core problem is perhaps somewhere in the update/upgrade process, and starting from scratch is the only thing that helped me. I've been running lean, too - just email, some news and travel apps, and one single game. But hey - I can email again without my blood pressure spiking and without it being faster to get in the car, drive to my office, check my email, and return home.