If my memory serves me right it's a cookie.

This was my understanding but I can't see any relevant cookies going over the wire. Looking at EPiServer.XForms.XFormData.HasAlreadyPosted(Page page) in ILSpy shows that it does in fact check a cookie if the persistance options isn't set to Database or the UserName is null. 

In this situation it checks for a cookie named "FormCookie":

private static bool CheckCookieForPostedForm(Guid formId, Page page)
{
    HttpCookie httpCookie = page.Request.Cookies["FormCookie"];
    if (httpCookie != null)
    {
        foreach (string text in httpCookie.Values.Keys)
        {
            if (text.Equals(formId.ToString()))
            {
                return true;
            }
        }
        return false;
    }
    return false;
}    

I'm testing as an anonymous user but there is no "FormCookie" present in the request or response on the POST of the form or the request or response on the Thank You page so I can't see how this is working.

Following the logic for anonymous users, if you're posting to the database and the UserName is not null, there is a Linq query which checks the DDS for a submission with a matching FormId and UserName. 

public bool HasAlreadyPosted(Page page)
{
	if ((this.ChannelOptions & ChannelOptions.Database) != ChannelOptions.Database || this.UserName == null)
	{
		return XFormData.CheckCookieForPostedForm(this.FormId, page);
	}
	if (Guid.Empty.Equals(this.FormId))
	{
		throw new InvalidOperationException("Cannot read the XFormData before the FormName property has been set");
	}
	DynamicDataStore store = XFormData.GetStore(this.FormId);
	int num = (
		from post in store.ItemsAsPropertyBag()
		where (Guid)post["Meta_FormId"] == this.FormId && (string)post["Meta_UserName"] == this.UserName
		select post).Count<PropertyBag>();
	return num > 0;
}

Looking in the database (tblXFormData), there are no NULL values in the Username column. Could it be that the this.UserName == null check above is failing, then it's executing the Linq query which comparing the username of an anonymous user to the usernames in the table, of which there is an empty one from the first anonymous user and reporting a false positive?