I have a hunch that the reason people are only starting to have trouble now is because everyone who zipped through in the first few days used cheats and/or Very Easy.

The people who don't take shortcuts have to plow through the campaign the regular way. I don't intend to turn the difficulty down because I want to prove that it can be done on Medium. At this point, it's a matter of personal pride.

I think you might approach difficulty in a different way than most people. I don't know, maybe you play while on speed or something; or maybe (hopefully more likely) your familiarity with your missions is hampering your objective perspective. I can complete the FS1 and FS2 campaigns on Insane, and I find Aeos Affair a challenge but still beatable. I thought Shrouding the Light was tough when I first played it, but after I figured out Blaise Russel's methods, it's not that bad.
PI, though, is simply frustrating. It's the kind of frustrating that causes me to give up on lesser campaigns and cheat my way through, just because I've had enough and want to see how the story ends. Fortunately for you, the story in PI is not only good, it's top-notch. So I have a love/hate relationship with the campaign -- the story is as fascinating as the difficulty is frustrating.

This is turning into the review I wanted to write when I finished the campaign, so I guess I'll just review what I've seen up until now:
1) A bit harder than I thought, but beatable once I adjusted my initial assessment of the difficulty. I thought it was about twice as long as it needed to be, though; I got really annoyed when I reached the halfway mark and heard there was still another half to go. Dogfighting for more than 5 minutes at a stretch gets boring.
2) Not that bad, but still kind of long. I appreciated getting the message about support ships repairing hull to 60%.
3) A cool mission, but the difficulty kept me from having fun with it. I died a couple times when the main action was over but the incoming PCA wings were trying to sanitize the area.
4) This one took me several tries until I ordered everybody to protect the Unut and just protected the Diomedes myself. I got really annoyed at how incompetent my wingmen were here.
5) This one was fun. I had a pretty easy time destroying all 18 ships, but the incoming fighters made it challenging. The main bug I noticed here was that someone destroyed the meson bomb almost immediately after it arrived, causing two conversations to overlap.
6) As I said before, challenging, but very doable. Finished it on the first try with the Deshret at 11%. It might have helped that I took Tornadoes instead of Tempests.
7) No major problems here, although it would have been nice if Command had responded immediately to Alpha 1's protest at chasing the Agni. I had to restart the mission because I zoomed over to try to scan it.
8) Very, very frustrating. I tried making my way toward the Amenemhet, dogfighting fighters and destroying turrets as the walkthrough said, but the Amenemhet always jumped out before the first engine reached 50%. The Phalanx wasn't a great help here, as the first shot takes a Thoth down to about 5% and then I have to wait before I can fire a second shot to finish it off. My wingmen were positively useless. I had to play this mission about a dozen times before I just decided to hang back and snipe at the Amenemhet using Trebs, ordering everybody to engage the enemy. I also thought the requirement to take out the nav and reactor in addition to the engines was rather arbitrary.
9) This mission was positively impossible, even though I was playing the patched version. I must have played it fifty times, getting the same result each time, plus or minus several seconds: the Minotaur went down shortly after the Thyrae arrived. I tried it in a pure bomber role, destroying all beams and ships; I tried it in a pure fighter role, intercepting all the bombers. (I thought it completely ridiculous, and utterly unnecessary, to have all those waves of bombers going after the Minotaur -- the bombs always got through even when I ordered every single ship to protect it.)
I finally realized that the bombers targeted the Minotaur only after the Khepri was destroyed, so I ordered everybody to protect the Khepri while I did my bomber thing. That, paradoxically, worked superbly. The Minotaur was still over 50% (and the Khepri over 30%) by the time the Saturn arrived; which led to an amusing awkward pause while the Saturn wore the Minotaur down with its beams.
I also thought it was wrong to have the protection of the Minotaur as a secondary objective. If its destruction triggers a mission abort, it should be a primary objective.
10) Same troubles as others have reported. In order to destroy both ships at the beginning, the execution had to be done perfectly (even though I followed the walkthrough). It was fairly easy to destroy either ship alone, but destroying both required a bit of luck. Destroying the Enceladus was slightly easier, even though I had to do all the work myself -- my wingmen were good for nothing other than being targets for its turrets.
One potential bug here (I didn't check, but you should probably test this) is that the navigation subsystem only governs warpout capability if it's set that way in ai_profiles.tbl. Since you didn't include an ai_profiles.tbl, your walkthrough wouldn't have worked. I didn't want to risk having to replay the mission just to test that out, so I always went for the engine.
11) This was not hard or frustrating so much as very annoying. I was clever enough to use Stilettos to knock out all the AAA beams in the mission, including the Nepits' and the Leviathan's, so my wingmen had an easy time. Unfortunately, I got swarmed by about 100 Herc IIs and Persei armed with EMP missiles on the way to the cargo depot, so I had to spent about 20 minutes (not kidding) fighting them all off. Then during the first time I got to see the Hybris jump in I started getting EMP'd again, causing me to miss the order to warp out and get vaporized by the Saturn.
12) Not as hard as the others, but I hit another mission bug here. When the Serket was disabled, I stayed halfway between it and the convoy so I could come to the assistance of either if needed. That caused a dead end. I looked at the mission in Notepad and found that the mission would only proceed after you closed to within 1200m of the convoy.
13) The most frustrating mission since 9. I tried going in through the bottom like the walkthrough said; it didn't work. I tried going in from the top, sides, front, etc. I finally opened it in FRED and looked at the waypoint paths. I ended up deciding that a sideways-downwards path on the right was the best approach, but I still couldn't make it work. I played it dozens of times, occasionally getting to the center but not out again. Finally I managed to do it by fluke as much as anything else. Then after the conversation was over, I was petrified that I'd get killed by the fighters, so I just ran away as far as I could.
It was here that I discovered that the escort list sexp trick didn't work reliably -- in fact, most of the time I got caught, it was by a ship that was
not on the list. I also found the failure debriefing very insulting here, considering the difficulty of navigating the sphere.
14a) No complaints.
14b) Not that hard, but the escort list trick still didn't work. And from a canonical standpoint, AWACS is supposed to reveal any stealth ship in non-nebula space, not just those within 2500m. Unless the AWACS only has a range of 2500m, which doesn't seem likely.
14c) The most frustrating mission since 13. My wingmen were absolutely no help at all in destroying any enemy fighters -- I always got every kill, or occasionally every kill save one. I even tried hanging back one time to see if they could do it themselves... even after 10 minutes, they hadn't gotten a single one. Then when I got to the Agni, I thought I had found another bug... no matter what I did, as soon as I got close enough to the Agni to hear the communications, I always got beamed. If I hung back out of communications range, the mission wouldn't continue. I finally figured out, after several frustrating restarts, that occasionally I could afterburn in and afterburn away without getting killed, but this wasn't obvious, nor was it explained why the Agni would randomly beam me. Then I discovered that, contrary to the walkthrough, I had to scan an Ancient fighter first, since they would invariably be destroyed by the time I scanned a bomber or a corvette.
I was rather annoyed that I had to scan everything personally, since the set-scanned and set-unscanned sexps have been in FSO since forever. And it was extremely frustrating to sit through 15 minutes of fighting and dialogue before I got to the point where I could try something different. And once, when I did everything perfectly, I got killed by the two Shivan wings at the nav point, which seriously, royally, pissed me off. Giving the player a serious risk of failure at the 20 minute mark, after considerable fighting, scanning, and dialogue, is an evil, evil, evil, evil move.
14d) It took me about five tries to escape this one successfully, which is completely unreasonable. All the more so because I had finally managed to get through the previous mission with 74% hull. If a player got to this point with a seriously damaged fighter, say at 10%, he would quite likely not be able to survive, and he wouldn't be able to replay the previous mission to try again (not that he should have to) because there's no briefing. Very, very poor design here.
EDIT: Now I've spent almost an entire day trying to beat 15. I tried doing it the walkthrough way; and I tried playing sniper with dual banks of Trebs. I have not been able to
live beyond 7 minutes, let alone get more than 10 turrets. It takes the prize from 9 as the single most frustrating mission in the campaign so far. If you can complete all the objectives on Medium within two or three tries, you need to post a video.