Ваша проблема не со днем недели (несмотря на то, что говорится в сообщении об исключении). Ваша проблема в том, что в марте 4444 года существует много сред, и анализатор не знает, какой из них выбрать.
Если вы добавите день месяца, чтобы сделать его однозначным, он проанализирует:
var format = "yyyy/M/ddd/dd";
var provider = new CultureInfo("en-GB"); // Have tried with several other cultures including Invariant
var datetime = new DateTime(4444, 3, 2, 1, 5, 6, 777);
var datetimeAsString = datetime.ToString(format, provider);
// Here datetimeAsString == "4444/3/Wed/02"
var x = DateTime.ParseExact(datetimeAsString, format, provider);
Ссылка