I've been noticing this issue a lot on my more complex SharePoint listforms. We are on SP2010 and IP2010.
The issue seems to manifest itself on a publish but we may not notice it for a while. I've had a few theories as to the course, but it never seems to repeat under the same variables.
I don't think I line up quite with rckurschner's experience. I've seen it happen on ists without people and group columns. I think there is some relationship with inconsistently modifying columns in both InfoPath and SharePoint, rather than just at one end - I am sure you all know that there are often reasons why you must make a change in one app or the other so you see the problem.
Most recently our 'title' column was remarked as mandatory - interesting given its an OOTB on every SharePoint list.
I've not had to delete the form in any of these cases. I am able to untick 'cannot be blank' and republish successfully. I take it that it's not that simple for you guys?
No solution, but wanted to chime in that there definitely is a problem!