Hi Patrick,
I use enlightenment as my WM and experienced this for a while sometime last year. It had something to do with NetworkManager and evo taking it's on/offline cues from that. I thought it was fixed in one of the 2.(1?)X releases, but it's worth a try if nothing else works. I would log into Gnome, then back into e whenever this happened.There's a toggle called apps->Evolution->Shell->start_offline but I've tried it both on and off without having any effect.
Not sure if this is the problem, but it may start you on the right track. --chris