I am only able to move email from my inbox to any folder when I am online. I have fully downloaded the emails which I have seen as the only recommendation.
The emails not fully loading is an annoyance unto itself but I have learned to live with it by going online getting the message, putting myself offline to mark them, and then going back online to fully download just so I am able to work with the emails.
This is for Outlook 2007 and I don't remember this happen in 2003.
When I had computer problems and my hard drive was wiped clean and then Outlook was reload - I ended up having to mark them all over again!! Though they did stay in their folders.
Is it possible to move emails to folders when in offline mode?