have the same issue
my fc keeps showing already deleted messages
battery pull.... done
delete fc re install it... done
install older version.... done
device wipe... done
phone wipe and os reinstall... done

nothing works for me