I've just got a Nokia 6610 (and very nice it is too) and have spent the last couple of days configuring it. As I have a months free internet usage (thanks Vodafone), I thought I'd make use of it. I set my email settings up (I use IMAP) and could send and receive emails, however, messages deleted from my IMAP server, weren't being deleted from my phone's inbox. This confused me for quite some time, and I couldn't find anything on the internet to help me so I fiddled with a few settings until I got it to work.

Within the E-mail settings section there are 4 options:
Connection settings - the incoming and outcoming options for the email servers
User settings - name, signature, new email alerts
Retrieval settings - what to receive (headers etc) and how many, IMAP folders to retrieve
Automatic retrieval - E-mail notifications and E-mail retrieval.

The Automatic retrieval details holds the key, it is badly described in the user manual as:
E-mail notifications — To automatically retrieve the headers to your device when
you receive a notification of new e-mail in your remote mailbox, select Auto-
update or Only in home netw.
E-mail retrieval — To have e-mail headers automatically retrieved at set intervals,
select Enabled, or if you only want headers to be retrieved in your home network,
select Only in home netw. Headers can be automatically retrieved for two
mailboxes at most. You can set on which days, at what times, and how frequently
the headers are retrieved in Retrieval days, Retrieval hours, and Retrieval interval.
E-mail notifications and E-mail retrieval cannot be active at the same time.

Quite frankly I didn't understand this when I read it first time, and I still don't fully understand it. What I do know, however, is that by choosing E-mail retrieval and setting it to "Only in home netw." a message is displayed on the screen which says "All e-mails are retrieved to mailbox when automatic retrieval enabled. Continue?" which led me to believe I was on to something. I set up some Retrieval days, hours and interval and then when chosing to connect a proper synchronise took place. I'm not sure if this is because some other settings behind the scenes were magically updated, or that this on its own was the key. To try and work this out, I set the E-mail retrieval back to disabled and re-connected and deleted emails didn't get removed, so I'm assuming that this is the key.

I'm not sure how much I want to use email on my phone, but I'm pleased to have worked out how to make it work.

Update:
More confused than ever. Whilst it worked once, and sync'd my mailbox, I then deleted some more emails from my server IMAP account and re-connected and nothing changed. New emails were received, but deleted ones didn't go away. However, if I delete an email from the phone inbox (and asking it to delete on the server as well) a proper synchronise seems to happen. This would appear to be the most reliable method currently.