The media-carrying book for the Collector's Edition of The Cutting Edge reproduces both sides of the release card for Record 1 of Blonde On Blonde. The front of the card gives the Shipping Date as 5-16-66, and on the reverse side the card is dated 4-27-66.  In other words, on April 27^th, when the card was prepared, the planned shipping date was May 16^th.  This date was still being cited as the release date by Sony in 2010, when they printed it in the booklet for the Original Mono Recordings box set.

It is just conceivable that an early US pressing reached a few shops during May, and that distribution was then halted pending further revision.  One correspondent tells me he bought a mono copy of the album in Virginia in Spring 1966, and he believes it was during May.  He has no corroborative evidence of the date, but remembers that for some time after, other people seemed to be unaware that there was a new Dylan album out at all.   He specifically recalls that

(a) his shrink-wrapped copy did not carry the sticker which was on copies he saw in shops a month or two later (see below), and

(b) the shop where he bought it did not have stereo copies, only mono. When the album got its proper release in late June it was reportedly in both mono and stereo formats, at least in New York record stores.

However, this copy is now lost.

Alan Fraser's Searching For A Gem website cites another correspondent who is certain that the album was indeed on sale in California in late May 1966 – see www.searchingforagem.com/1960s/MonoLPs007.htm . Again, there is no physical copy of the album to back this up.

If there really were US copies released during May, then I would expect them to contain an earlier mix of "4th Time Around" than that on the familiar US mono album, as they would have been pressed several weeks in advance of the final overdub session for that track. 

However, the fact that no such US-pressed copy has surfaced in over 50 years suggests to me that the above reports are almost certainly mistaken.