Another idea that occurred to me was a lack of label for presumed trolls. We could show the author's current level next to their name in the by-line header. We would display no level for anonymous nor for sub-zero-XP authors.

That reminds me to How about coloured names based on xp's?, an idea that got very little support because it would cause a raise in votes based on nodes' authors, not its actual contents (and personally, I've taken the opposite approach and did some CSS to completely hide nodes' authors).

As a side note, I'd like to point out that the labeling jdporter suggests shouldn't be blindly applied to everyone whose XP is less than zero. Some user's first messages could get a negative rep for other reasons than trolling. I'd label if XP < MAGIC1 and posts > MAGIC2 (for some low values of MAGIC1 and MAGIC2, like -9 and 3 for example) or even if posts/XP > MAGIC (with MAGIC around -3).