This was bugging me a bit, so I went digging again, and I think I found the answer to my "Blue Monday" issue, and maybe the better way to search MusicBrainz for earliest release dates...
By hand, I queried for the Artist and Song, narrowed down to either Album releases or Single releases.
Blue Monday AND artist:New Order and type:album OR type:album
This query got the song on page one, and parsing the output finds the correct earliest release date of 1983. Yay.
Theoretically, the "types" should also include Soundtrack and Live and EP and the list goes on.
Basically, avoid Types like Compilation and Live which are very unlikely to contain Earliest original Release Dates.
Now I just have to translate this into my Python script. wxdude, if you're using Python let me know if you want my code snippets to save a little time.