So early on it wasn't a problem, my guess is that trolls probably didn't really appear until AOL.
The real Internet is not HN, it's not Facebook or Livejournal. It's 4chan and the comments on Youtube. That's what we built, that's the glorious future, the pinnacle of high tech, the global collective consciousness. How proud should we be?
What's really depressing to me is going to visit the San Francisco Chronicle website, CNN or wherever, and seeing the comment space overrun by arrogant idiots who think they're superior to 4chan, or would if they knew about it. I would far rather be trapped in a lift with a bunch of /b/tards than the over-earnest moralists (of all political stripes) that attach themselves like limpets to the mainstream news and political sites.
You can't compare that to YouTube comments at all. 4chan's about lulz, not pure unadulterated stupidity. They're not the same at all.
And anyway - not all "trolling" is created equal, IMO. Smart, organised, (dare I say) funny trolling beats random hate and idiocy anyday. I haven't noticed 4chan moving with any particular malicious intent; they just try to amuse themselves, and the causes are as often defensible (Scientology, Sarah Palin mails) as not.
We're always going to have trolls. If 4chan sets the standard for trolling I think we've done pretty well actually. At least they're intelligent.
The real internet isn't HN, but it's also not 4chan or Youtube. The real internet is the internet -- the whole internet. Tautological but true. As long as there's always some readily-accessible part of the internet without troll problems, then I'd say we're doing okay.
The real progress, though, would be figuring out how those civilized parts of the internet can stay civilized. Some forums have a small population. Some forums have a strong sense of community and ban-happy moderators. Some forums have downvoting, although that doesn't seem to stop persistent trolls. If you've got a better way, discussing it would be fun.
That said, the caliber of trolling may have been slightly higher. :)
Found... don't know if it counts as a troll, tough: Google for "The Strange Case of the Electronic Lover"
I'm old enough to remember that there were trolls on Usenet before AOL built its gateway to Usenet.
I'm pretty sure that verifying the earliest use of "troll" in the sense of this thread and comparing that with the date of AOL's gateway opening would confirm this.