The chord progression that I'm playing goes as follows:
Am Dm E Am , and I just repeat this progression.
Here's my question. I'm soloing over this progression using the C Major scale and it works just fine. However, the chord "E" isn't part of the C harmonized major scale, is it? Shouldn't I be using an "Em"? Can someone please explain to me why this E chord works well in this progression? And would I be able to use a different scale to solo over this (mixolydian, etc.)? Thanks in advance.

First of all, you're not soloing over this progression in C major, anymore than you're soloing in B Locrian. You're basically using the A minor scale. The A Minor scale (or more specifically, the A Natural Minor scale) IS the same as the A Aeolian Mode. Yes, the A Minor Scale/A Aeolian Mode shares the white keys of the piano with the C major scale (among many other modes), but it's step pattern is different and it sounds different. Minor sounds different than major.

Okay, now, a harmonized A minor scale would have the chords Am Dm Em Am for your progression, yet this scale is working over E major. How is this possible? Good question! First of all, IF IT WORKS, IT WORKS! Theory only explains what works, it doesn't control what will work. Experimenting and breaking what would seem to be the rules leads to new things that work, and then theory has to change to encompass that. Still, established theory can be very, very useful. Different people look at music different ways though, so there isn't always one right answer.
My simplest explanation:

First, be aware that most basic chords are made by taking the 1st, 3rd and 5th notes of a scale and playing them at the same time.

The E chord has the notes E (the first note) G# (the third note of an E major scale) and B (the fith note of an E major scale), but you are playing an A minor melody which has a G in it (not a G#). You are playing a minor third note(G) over a chord with a major third. This playing of a minor third over a major third only happens to be one of the coolest sounds in music, and is part of the basis for the blues. This minor third played over a major chord is a great combination (in the right context) and that's one way of looking at why that A minor scale was "working" even when played over the E major chord.
_________________________________________

You might have noticed that your progression doesn't fit perfectly with any mode [harmonically]. That's a good lesson. Progressions don't have to stay within a mode. In fact, most songs DON'T stay entirely within one mode, harmonically speaking.

While progressions (and certainly songs) don't have to stay within one mode, scale, or even key, your progression of Am Dm E Am does completely fit within one well known harmonized scale: A Harmonic Minor.

If you take your A minor scale ( A B C D E F G A) and raise the 7th note a half step, you'll get A B C D E F G# A. This is the A Harmonic Minor Scale, and you can see it includes the G# that will yield the E major chord when harmonized. This isn't a scale you'd want to use everyday, but it's fun to play around with and can really impress your jamming partners that don't know much theory. If you've ever heard 'In the Hall Of The Mountain King', you'll recognize this sound immediately.

You could play A Natural Minor over the Amin and Dmin of your progression, and then when you get to the E, play A Harmonic minor (simply play G#s instead of Gs). That sounds kind of cool. Alternately, you could play A Harmonic Minor over the entire progression, yielding a very different sound and feel compared to your original solo in A [Natural] Minor.

A minor pentatonic works pretty well over the whole prog ( A,C,D,E,G ) or A Blues ( A,C,D,Eb,E,G ). I like DMT's harmonic minor suggestion , especially over the E major chord .

Let's look at it chordally. Your root (the chord you start and stop on) is an A, and in this case it is am, so it is a pretty safe bet that you are playing in am.

Sooooooooooooo, you are playing in the key of am. If you think of am, dm, and E as I, IV, and V (which oddly enough is the progression at the heart of almost ALL music in the wester world) it becomes clear. In a minor key, the I chord (or i chord as it really should be written) will always be minor (and here it is, am)and the IV chord (iv)will be minor (hence the dm), BUT you will never have a minor V chord (so in this case the E is major).

V chords always set up a tension to resolve back to the I chord because the third (in this case the G# of the E chord made up of E(root), G#(3rd), and B(5th) )leads one's ear back to the root.

This is also the reason why using the harmonic minor scale would be an option because at the heart of that scale is a raised 7th, our G#, which sets up a lot of tension needing to be resolved by returning to the root of the scale (in this case a). Don't be confused, it is the 7th degree of that scale AND still the 3rd of the V chord. Same note, same need to land back on the root.

Go easy with it though, overdo it and you'll draw a lot of Yngwie jokes because he made an entire career out this scale.

That, with what has aleady been said, should sufficiently muddle the waters for ya !

It works well, as you said. The A natural minor is used over the same Am to E progression used in a lot of Latin and mariachi music. However, I like using the Am scale and just raising the 7th to G# just over the E chord. In fact, you can hear Santana doing this in "Smooth". It sounds very cool.

By the way, DMT, he's not soloing in B locrian because no B chord is used. A mode is starting off on the ROOT....so, in order to be soloing in B Locrian, he'd have to be basing the progression around the Bm chord.

Beware that a certain swedish dude sort of killed the harmonic minor scale. So be careful not to play it to fast. I think there's a major V chord in Hotel California as well. Treated very nicely in that song. Good song to jam to if you wanna practise that change.

Oops...sorry, DMT. That's the problem with logging in here after gigs! Too tired and I'm winding down at that hour!

No problem, I figured it was something like that. My original post was probably too long for best clarity anyway.