Actually during the beginning of WoW flasks did disappear after death, but that's a bit OT...
Naxxramas was hard for a variety of reasons, and not just because of how it was tuned. You have to factor in that the resources we have today simply did not exist back then.
When a raid comes out today on retail, it has already been cleared by numerous guilds on the PTR in all modes. In addition, the boss tactics and strategies are made available as guides and youtube videos, so you can watch how it's done before you even enter the raid. Every part of that raid has been datamined for months by Wowhead and mmo-champion, there's no secrets or surprises to it. The entire thing is exposed and all the information is available to everyone on demand before it even hits live servers. But this wasn't something that existed back during Vanilla. No one cleared Naxx on the PTR. Youtube was still brand new and people weren't uploading how-tos. Many guilds kept their strats secret, wanting to be coveted and worshiped. The info just wasn't there, and many people went in blind.
Another difficult aspect was computers. Most people didn't have high end computers in 2006. Internet speeds were much slower as well, and realms were known for being quite unstable. 40 man raiding wasn't particularly friendly, and lag and disconnects were quite common.
Then there was the fact that Naxx was balanced around full consumables, which was far too expensive for most to do. The private server community may not have an issue farming and running with max consumes for progression on every single boss attempt, but this was not an option for many guilds on retail. Watch old naxx vids - You'll see a Flask and Wizard Oil/Stones definitely, but potions? Probably not, at least not on the easier fights.
Finally, the biggest aspect of difficulty to Naxx was the lack of knowledge people had about the game and their class. Once again, watch old Naxx videos. How many people do you see in crappy gear setups? Bad specs? Improper use of downranking or mana regen spells/consumes? It's all there. Even top guilds like Curse had issues. The mage PoV ran as Frost in full Tier 2 with a spec that included Ice Barrier on Patchwerk. As you can imagine, there were a lot of resists and a lack of damage. I have even seen a vid of a Lock in T2.5 using a rotation of Immolate, Untalented Corruption (2 second cast) and Drain Life on Grand Widow. I'd be surprised if he even cracked 50dps. The other lock that was visible in the vid was doing the same thing. It's a fact that most people didn't know how to play with maximum efficiency, theorycrafting was pretty new and very niche to only a few elitist guilds. Class guides weren't readily available or poorly done. BiS gear lists did not exist. These players were clearly dragging their guild down, but how many really knew that?
So let's recap what made Naxx truly difficult:
- Lack of knowledge for bis gear/spec setups
- Steep difficulty curve
- Limited info of boss mechanics
- Balanced around max consumables
If players had the info we have today back then, Naxx would not nearly have been as hard. But I suppose that's what makes Vanilla so appealing to many.