EDT is for the USA, which is to the west of the UK. the sun rises in the east. so the sun is overhead in the UK before the USA. so you need to add 4 hours to EDT to get GMT. this is why i need to call my parents (in the UK) by late afternoon, or they are in bed. in other words: "EDT +4 is GMT".
now the source for this is at http://bazaar.launchpad.net/~dateutil/dateutil/trunk/view/head:/dateutil/parser.py and a comment that seems to be associated with parsing GMT-0400 says
# Check for something like GMT+3, or BRST+3. Notice
# that it doesn't mean "I am 3 hours after GMT", but
# "my time +3 is GMT". If found, we reverse the
# logic so that timezone parsing code will get it
# right.
which means that GMT-0400 is equivalent to "my time -4 is GMT". which is not the same as above.
also, if you look at the code, a trailing (EDT) is processed after this, and so takes priority. and i think that the third case, with the final, simple -0400 is processed as you expect.
in other words (it seems to me, from scanning the code) the GMT-0400 form is working as the code documents, but not as you expect. that line is not equivalent to the other two.
i have no idea why the code works this way; i am just reporting what i read.
finally, note that the general approach in that code is to work through the entire date string chunk by chunk, applying different logic to different places. there is not that much checking to make sure that the logic in different places is consistent (so no error is thrown for the apparent contradiction in the first line). personally, i would prefer a library that uses python's own date parsing routines, but tries different format strings - i suspect that would be more reliable (but perhaps less flexible).
UPDATE i had forgotten about this post, but a while after after writing this reply i wrote simple-date to handle parsing of timezones. it takes an approach more like i said i preferred - instead of trying to be clever, it searches the pytz database for matches.
2012-05-13 00:00:00+04:00 2012-05-13 00:00:00+04:00 2012-05-13 00:00:00-04:00