I'm venturing in unknown territory here...
I am trying to work out how hard it could be to implement an Email client using Python:
Also I'm wondering if all protocols are easy/hard to support e.g. SMTP, IMAP, POP3, ...
Hopefully someone could point me in the right direction :)
The Python language does offer raw support for the needed protocols in its standard library. Properly using then, and, properly parsing and assembling a "modern day" e-mail message, however can be tough to do.
Also, you didn't say if you want to create a graphical interface for your e-mail client -- if you want to have a proper graphical interface -- up to the point of being usable, it is quite a lot of work.
Local e-mail storage would be the easier part - unless you want to properly implement an mbox file format RFC-4155 so that other software can easily read/write the messgaes you have fetched, you can store them in as Python Objects using an ORM or an Object Oriented database, such as ZODB, or MongoDB.
If you want more than a toy e-mail app, you will have a lot of work - properly encoding e-mail headers, for example, server authentication and secure authentication and transport layers, decoding of the e-mail text body itself for non ASCII messages. Although the modules on the Python standard library do implement a lot of that, their documentation falls short on examples - and a complete e-mail client would have to use all of then.
Certainly the place to start an e-mail client, even a toy one, would be taking a look on the most recent RFC's for e-mail (and you will have to pick then from here http://www.ietf.org/rfc/rfc-index since just looking for "email rfc" on google gives a poor result).