bmike I'm putting this into our bug report list and will investigate this further.
Previously, this was occasional issue that affect cross domain embedding only (actually this is expected when the form is embedded across different domain) or when the server is being configured to use extensive caching or not having PHP session configured.
However, now it seems to be more persistent indeed, even when the form is within the same domain. I'm marking this as high priority issue now. Thanks for this!