David and Katherine Goodwin

changes to previous comment as < > was striped by html code

first:
walk your user's Maildirs and check if messages haven't NUL char in it.
as example:

#/bin/sh
curd=`pwd`
while read dir; do
cd "$dir"
find -type f | while read file; do
tr -d \\000 < "$file" > /tmp/tempfile
chown --reference="$file" /tmp/tempfile
chmod --reference="$file" /tmp/tempfile
mv -f /tmp/tempfile "$file"
done
cd "$curd"
done < list-of-maildirs-dirs


second:
it still wont work if any errors in headers

I suggest this script if you have altnamespace: yes
(I changed cyradm to not ask password, instead read it from file)

#!/bin/sh
function _sent ()
{
echo "$1" | cyradm localhost | sed 's/localhost> //g'
}
USERS_FILE=$1
[ -f $USERS_FILE ] || { echo No users file; exit 1; }
exec 5<$USERS_FILE
while read -u 5 user; do
_sent "cm 'user.${user}'"
_sent "sam 'user.${user}' cyradm all"
mailutil transfer -verbose -merge append \
'{imap-host:143/imap/tls/novalidate-cert/readonly/user='$user'}' \
'{localhost/imap/user=cyrus}user.'$user'.'
MMBOXES=$(_sent "lm 'user.${user}.INBOX.*'" | sed 's/ (\\[[:alnum:]]*) */\n/g')
OLD_IFS=$IFS
IFS=$'\n'
for mbname in $MMBOXES; do
newmbname=${mbname#user.${user}.INBOX.}
_sent "rename '$mbname' 'user.${user}.${newmbname}'"
done
IFS=$OLD_IFS
_sent "rename 'user.${user}.INBOX' 'user.${user}.InboxMail'"
echo -e "\n\nRECONSTRUCT:"
sudo -u cyrus /usr/sbin/cyrreconstruct -r user.${user}
echo
read -p "Done user: ${user} ?" ans
grep -q '^[yY]' <<< $ans || { echo "Exiting..."; exit 0; }
done