Jeremy/Kurt - I'm in the same boat. Have 75K URLs I'm trying to check as part of a link pruning project.
There's actually another Moz Forum post (http://moz.com/community/q/mass-404-checker) that has a very similar ask and responses are largely the same.
Below is a link that was mentioned in this post, but I've tried it a few times and it keeps getting hung up on any list over 100 URLs.
http://www.tomanthony.co.uk/tools/bulk-http-header-compare/
Below are the only other ones I've found, but again are limited to 100 or less URLs.
http://httpstatus.io/
http://tools.seobook.com/server-header-checker/?page=bulk&typeProtocol=11&useragent=1
I feel like this is such a common problem for people trying to do any kind of mass back link research project. I'm also looking for something that checks follow vs nofollow so I can further narrow my list.
Maybe we should just create the tool? : )