What mailbox format are you using? What's the output of:
Using sdbox
doveadm mailbox status -u user@host.com 'uidvalidity uidnext' '*'
There is one folder with uidvalidity=0:
Trash uidnext=696 uidvalidity=1169866046 Notes uidnext=1 uidvalidity=1406044590 Sent Messages uidnext=112 uidvalidity=1169866046 Drafts uidnext=62 uidvalidity=1169866046 INBOX/my pictures/Nelson uidnext=1 uidvalidity=1406044592 INBOX/my pictures/Orlando uidnext=1 uidvalidity=1406044593 INBOX/my pictures/Rexbutg uidnext=1 uidvalidity=1412469718 INBOX/my pictures/Jared uidnext=1 uidvalidity=0 Deleted Messages uidnext=474 uidvalidity=1406044591 Deleted Items uidnext=2354 uidvalidity=1396558447 Sent Items uidnext=312 uidvalidity=1396558446 Junk uidnext=1 uidvalidity=1241816596 Junk E-mail uidnext=269 uidvalidity=1396558448 INBOX uidnext=38973 uidvalidity=1168294174
Is there one with uidvalidity=0 value? That shouldn't be happening.
Thanks.