Question: Let's say user A follows user B, and B follows A. I want to know the exact date A started following B and viceversa.
Is this information stored on twitter? Can I retrieve it using the API?

To clear out: The point of this question is finding a way to know who followed who first.
(I'm assuming both A and B deleted the notification e-mails)

Answer: 
No Ignacio, you can't. You just can know who follows who but not the date the follow started.

Looking at the API, there's is no way, there are two calls to get the followers:

User Methods/statuses/followers

and

Social Graph Methods/followers/ids 

Neither of them returns dates or even a serial that would let you see who started following first. Really, **there's no indication that twitter is internally storing this information**, neither in the API nor Twitter's web interface.
It is possible to do this, but impractical. When you call the followers API you can page the results. Each returned object contains `next_cursor` and `prev_cursor` items. These refer to the first and last records in the next and previous pages. These values are time based and can be used to calculate the time that the respective users followed you.

It follows that, if you set the page size to `1`, you can walk through the list of follower IDs one at a time and the `next_cursor` value will allow you to derive the follow time for the next record.

This is reasonably simple to implement, however, in practice, you'll very quickly hit Twitter's API rate limit.