The way I was taught to determine a song's key is fairly straightforward: You list the pitch class (all the known pitches in a melody) and use that to determine the key. In this case, we have a collection of chords instead of a melody, so let's use that. I'm doing this more or less in my head, so please consider this a rough draft and let me know if there are any errors!
A bit of theory:
A song's key can be thought of as, rather than a list of what pitches are allowed, a starting place. There will often be accidentals - notes outside the key. What we want to do is find the key that's generally the center of the song. But if most of the pitches are in the key, it's probably right.
Theory is meant to describe music, and music is composed based on what sounds good. We use the theory aspect to (1) write stuff down, and (2) describe and maybe understand the music.
The difference between A# and Bb:
I'll do what I can to keep this simple, but feel free to skip ahead.
In the tuning system we use, they're enharmonically equivalent (read: The same thing for our purposes) but there are other tuning systems where this wasn't the case. For now, just remember that you want to have one note in a key for each named note and no more.
A B C D E F G
A B C# D E F# G#
E F# G# A B C# D#
On to the music:
E - C#m - G# (or Ab?) - A (Where Is My Mind - Pixies)
Gives us the following pitches:
B C C# D# E G#
I think this puts us in the key of E major. (You've probably noticed that there's a C and a C# here - right you are. C is an accidental note, outside of the key. This can make the G# chord want to resolve to A.)
C#m - G# - A - E (Say It Ain't So - Weezer)
A B C C# D# E G#
Again, the C is an accidental, and outside of the key. Even more interesting, the B, C, and C# are a short chromatic run. Cool! Listening to the song, the key sounds like C-sharp minor to me. (C#m is also the relative minor of E major - that means the keys have the same notes but start from a different point.)
[Note: The version I can find on youtube are in Cm, the relative minor of Eb major, but I'm using your original key here.]
Dm - A - A# (or Bb?) - F (Luckiest Man - Wood Brothers)
A Bb C Db D Eb G E F
I'd guess this is in D minor (relative of F major, a key with one flat note), and I'd notate it that way. You'll note that the B flat chord sounds out of place, and resolves nicely to the F, it keeps the chord progression moving forward well.
Playing notes in the D minor pentatonic scale works well over this progression, and you can't go wrong playing D here, and A is nice except during the Bb chord. (I picked up a guitar for this one, it's a nice guitar piece.)