.... and I don't mean for just the solo or melody. Anyone have any ideas or know songs or have written songs that use both the chord progression and melody of a scale other than the natural major and natural minor scales.
[U]        | |                     [/U]
[U]        |/     .-.              [/U]
[U]       /|_     `-’       |      [/U]
[U]      //| \      |       |      [/U]
[U]     | \|_ |     |     .-|      [/U]
      *-|-*    (_)     `-’
Well harmonic minor is the easiest "exotic" scale to find used in music (many people don't even think of it as exotic, but you were asking about scales other than major/natural minor)

The music of my teacher and friend, Tom Hess (www.tomhess.net) has some rather exotic keys, solos and phrases all over the place. He frequently writes and solos over progressions in lydian, melodic, harmonic minor and uses other exotic scales like hirojoshi, hungarian etc... Its really cool stuff actually. Check it out!

Mike Philippov .