Ok so here's another contender that I just remembered and found some mp3s for. Alex Skolnick from Testament. Although I don't really like the current stuff, his stuff from the Souls of Black album released in 1990 was great.. Very Maelmsteen-like in many places.

Here's a youtube of my favourite song from that album:
http://youtube.com/watch?v=9Ir6N2ksDG0