here's my two cents it really depends on your amp and your woods.. I've got a mark 5 too, I've had hard times dialing out the harshness with my Painkiller equipped 7 string guitar.. It had too much output, too much upper mid spike and trebles, it was thin and annoying even being a 7 string.. the woods on my guitar are - mahogany body+wenge top, rosewood neck with plated ebony + ebony fretboard.. so, something like a les paul custom with more presence and uper spike (at least when we compared my guitar to my friends LP Custom there were really huge similarities just to give you a picture)
I recently swapped the bridge pickup with a Holydiver, I must admit I am still messing with the height due to the low B, but I am almost 'there'.. what it did is that it is definitely not driving the amp like mad the PK had just too much juice and trebles, I feel like I have more control of my guitar now due to the FQ side being shifted rather to lower mids and a full bodied sound.. If I ever had an opportunity and cash to experiment, I'll fetch me a blackdog bridge pickup which should be even less hot but singing with more overtones and more musical (even though I hate to use this term cause its usually the player who should be musical, lets just stick with inspiring:) )
The thing is that- I did the same as you, I asked here, I got some ideas in reply but at the end of the day, your ears are the best judge.. that specific guitar, with that specific amp and cab needs a specific pickup.. If you'll find it, you'll know that's IT! :) go and try it out
from my perspective, i know i'm done at least for now with looking for the bridge pickup, next up is a swap for a VHII neck .. to really cover a broad area of sounds :)
oh and asfar as the mk5 is concerned.. you'll probably get that sound you mentioned in these two videos with getting EL34s for your power section and using CH2 crunch or maybe edge mode.. i somehow find myslef mostly on this CH2 from some reason it just sounds fuller and more appealing..