Realistically, we're just about into July, here.
So you're talking 2 months, which is not very long to be in the market job hunting, nowadays.
Most people are finding it's taking longer than that to go through all the applying, interviewing, and then actually receiving a suitable job offer which one finds to be acceptable.
So the point is for the most part, moot.
However, the stipulation is regarding actually working somewhere else during that time period, not regarding accepting an offer from somewhere else during that time period. They just want to make sure you're not working for someone else while still technically an employee of theirs. Realistically speaking: fu-k'em. It's every person for themself, and they're not going to come after you for simply accepting an offer.
As to negotiating a start date with the new employer, you'll have told them your reason for leaving during the interviewing process (and neither a layoff or VSP is anything to be ashamed of...it's happening a lot lately, and hiring managers understand), and if they like you enough to extend the offer, they will be willing to wait, especially if it's as short a period of time of one or 2 months.