I am currently using 2013.2.611.45 with .Net 4.5 new unobtrusive validation
Your demo video is a little different then what I am describing. Say you search and select "Around the Horn", then before you click the submit button you remove it by clicking the little x and THEN submit it. The page comes back as valid because it thinks you still have that value "Around the Horn" is
in the list.
I have also found a second issue that if you add items to the AutoCompleteBox solely from the client side that the required field validator doesn't think anything is in the box until you add an item the manual way. So doing something like below will show required field validator to show even though you have added items.
var entry = new Telerik.Web.UI.AutoCompleteBoxEntry();