Yo Key. The Guitar Grimoire is a great book for this stuff.
This is my technique for approaching scales and modes. It's been helpful to several people I've worked with on this stuff. You may or may not want to look at things this way...that's up to you.
First of all, learn the theory behind the major scale. I think it's helpful if all of your knowledge anchors from a base point like that. This is the same theory that you'll need to learn in order to build and understand chords and you may already have a good foundation here. The most important thing to learn is the actual intervals. Start with the root note and learn what a major second, third, a perfect fourth and fifth, and a major sixth and seventh sound like in relation to it and how to finger them. Learn them in higher octaves too obviously. If you've been playing extended chords you'll be familiar with the sounds and you should learn to find them either on adjacent strings or along the same string. Knowing the intervals in this way will get you around the neck alot better and help you tremendoulsy when building chords.
Now when you're ready to learn the modes, just think about altering the intervals to get a different sound. Lower the third and seventh a half step to their minor intervals and there is the Dorian mode. Change the 3rd and 6th to minor intervals by lowering them a half step....there's the harmonic minor (not a mode, but it's easy to think of it that way). Lower the seventh a half step as well and there's the Aeolian mode. Take the second down a half step as well and there's Phrygian. (You can find fretboard maps of the scales at this website:
http://jguitar.com/scale?root=E&scale=Phrygian&fret=0&labels=none¬es=sharps )
I think it's helpful in your improvising and soloing to know what makes the modes different and exactly what intervals are different among them. That way you know what sort of chords and rhythms they work over too.
Simply playing the major scale but starting on a different degree is a surefire way to confuse yourself about the use of a mode....but hey it works for some people.
Take the 5th degree of the harmonic minor scale, and you have phrygian dominant. (Or just take the phrygian mode and raise the third back to a major third) That is a very exotic sounding scale that is common in metal.
Another exotic sounding scale is the diminished scale. It is an eight tone scale that you can either play as a strict alternating whole step / half step pattern or a half step / whole step pattern. The neat thing about this scale is that a single scale will work in several different keys (you can't play that pattern 12 different ways....only 3
) Sometimes you've got to experiment a little.
Sorry for being so long winded. I just like talking about scales.