I think my preference is that it works instantly, but have some sort of indicator that it is syncing working. Users should be able to see when it is safe to assume state is consistent with what is on the server.
And thus we get back to the need for Exchange Active sync icon from the Pocket PC era! I have finally lived long enough to see a full tech cycle go from new hotness to duh everyone does it this way to a good if boring option to that's so lame and worse, legacy, to what's that?