v8 and SpiderMonkey have the same issue. I've reported to them as well.
v8: https://bugs.chromium.org/p/v8/issues/detail?id=7117
sm: https://bugzilla.mozilla.org/show_bug.cgi?id=1420028

Some tests failed on Ubuntu. That's because toString() outputs Local Mean Time, like 'Fri Oct 12 0001 21:23:35 GMT-0752 (LMT)', when the date is before the standard time zone was introduced in that city. The problem is that the displayed time zone GMT-0752 is inaccurate. The actual time zone is GMT-07:52:58, which is used to calculate the local time 21:23:35. Thus when parsing this string, there's a 58 second discrepancy. It seems the spec assumes that time zone is always a whole minute.

I think this can be fixed in either of the following two ways, but they both violate the spec:

1. Allow Date.parse(x.toString()) and x.valueOf() to differ by less than 1 min. (violates 20.3.3.2)
2. Allow x.toString() to output GMT offsets with seconds, if the second part is not zero. (violates 20.3.4.41.3)

/cc @bterlson @dilijev

Re: xplat test failures, in the short term you could split the test into two separate test files, move the cases that have xplat failures into the second file, and tag the one with xplat failures exclude_xplat.

However it would be better to actually solve this problem before merging this change.

In terms of how to solve this problem:

(2.) we cannot violate this part of the spec. I think that behavior will be depended on much more readily than 1.

(1.) Rather than violating the spec on whether those values agree... Can we manipulate the value returned in LMT by rounding or truncating the LMT offset from UTC to the minute (up/down/nearest) so that those values are consistent? Since the actual time and time zone might be implementation-defined (down to the minute so that we can follow all of the spec rules) making sure that we don't have a discrepancy between these two in the number of seconds would solve our problems without violating the spec in any way.

/cc @obastemur

Please disable the neg. year tests on xplat. TLDR; I had initially implemented with BC support on Linux (bunch of tricks involved) but wasn't enough for OSX (different system / different source of random tz data for years with no actual tz).

Yes we probably can't have xplat tests for negative years which exactly match outputs on all platforms for the reasons stated above, however we can test that our implementation is spec-compliant on points (1) which is already tested by most tests, and (2) by testing equivalence of those two operations, rather than their actual values.

@dilijev @obastemur Sorry for the long delay! I was kind of busy in the last month.

I just pushed some commits which, I think, have fixed the remaining issues. I split the tests into two files (toString() vs toUTCString() and toISOString()). The former depends on time zone, so it has exclude_xplat set, while the latter should pass on all platforms.

To test the potential impact on performance (mentioned in #4300), I use the following benchmark code:

let arr_datestring = [];
for (let d = Date.parse("1000-01-01T01:02:03Z"); d < Date.parse("2017-11-27T10:11:12Z"); d += 1000 * 60 * 60 * 4) {
    arr_datestring.push((new Date(d)).toString());
    arr_datestring.push((new Date(d)).toUTCString());
}
let len = arr_datestring.length;
let result = 0;
let start = Date.now();
for (let i = 0; i < len; i++) {
    result = (result + Date.parse(arr_datestring[i])) % 12345;
}
let perf = Date.now() - start;
console.log("result: " + result + ". Time: " + perf + " ms");

The result for current release/1.8 branch is:

result: 3975. Time: 4213 ms
result: 3975. Time: 4264 ms
result: 3975. Time: 4287 ms

The result for DateParse_zero_padded_years branch (this PR) is:

result: 3975. Time: 4198 ms
result: 3975. Time: 4075 ms
result: 3975. Time: 4087 ms

It seems it even gets slightly faster, so I think probably the runtime cost for this fix is negligible.

I will squash the commits if it looks good to you.

@xiaoyinl thanks for this! I have couple of minor requests.

The rest;
LGTM

@dilijev @obastemur Thanks for the review! I have added the tests you mentioned, and commits are squashed.

Testing internally before merging.