I can only think of the ones that I couldn't finish because I wouldn't pump the number of quarters it required to finish, but still:
Magic Sword
Willow
Terminator 2 (2p dropped out when I almost beat it as a kid, so when I died at the very end (in front of the molten metal container), I would have had to continue from earlier)
Double Dragon II
I always remember NES games being the ones that were, at times, ridiculously difficult due to good (if slightly cheap) design (Ninja Gaiden/II/III,Battletoads), or due to bad/horrible/wretched design (Silver Surfer, Double Dragon III, Fester's Quest).