The taller form of Mahonia should be native to your area and will grow in deep shade. Evergreen huckleberry and leucothoe (sp?) are also native. I get a lot of bird-planted laurel in my deep shade which grows pretty quickly - can be a nuisance I hear but so far I'm just letting mine establish as a polite neighbor screen where they show up. I like the idea of a variety - maybe even with some sword fern at the foot of whatever you plant for added depth (if not height) and perhaps some snowberry - it is deciduous but the berries hang on through winter and it creates a bit of a tangled twig screen. Another thought is to create some brush piles against your fence now and then - good for the wild critters and could be temporary blocks while waiting for your plantings to grow.
It is always good to plan ahead - if you don't own the view, you really can't complain about what happens to it.
