Well it depends a bit on what shape majors your learning, some of the ones I use are all 3 notes per string shapes, which are great for legato. Look under the spider exercises thread for some 3 note major scales! Anyway the keys are the same as where you will find the chords basically speaking. Try and improvise and work on phrasing. Also see how you can fit licks in on different rhythm patterns.
enough with that insanely long quote.
i forgot about my three note per string scales! i learned them a while ago but i forget them. i'll take a look at them, i have a feeling they'll be a lot more useful than the traditional scale patterns. also, i'm finding it much easier to learn the scales in new keys now. after only one day i'm starting to not see the scales as C major scales anymore, and rather just patterns. i also realized that all i have to do is find all of the say, d notes (if i'm playing d minor), and then i know exactly what scale pattern i have to play since i know my root notes. before i was trying to memorize them in relation to the C major/A minor scale, but its a lot easier just using your root notes.
improvising is something that i do all the time. also, after working on my scales so much now, i'm finding i'm using them a lot more in rhythm type stuff as you said.
i've also been doing the spider exercises. very difficult to play fast! i haven't even attempted anything over like 100 bpm on the first and 80bpm on the second. they're good exercises though.