Man HoMM4 is best story. You are impatient and skipped through all the big scrolls that have such a good read that's why you don't remember anything.
Heroes online obviously sucks. It's just a moneymaking machine, zero value what so ever.
Cutscenes, meh! Read the story! -_-
As for Warcraft, ingame story is bad compared to Blizzard high standard, in war3 it was okay, but when it comes to warcraft, books are the best.
With custom games, you refer to just pure gameplay on random maps, or specifically tailored scenarios with a nice short story and plot? If it's first... meh...