Tessa, I've been thinking about this a lot lately. Admitting to myself (finally) I was trans came after a *lot* of clues that I buried deep and safe where I couldn't see them... and along with them, in the mix, was *me*.
When I was four, my dad took me shopping for my birthday. The only thing I really wanted was a baby doll up on the top shelf. It had a number of accessories and it fascinated me. I needed my dad to get it down for me so I could look at it... he told me it wasn't a boy toy and that I should get something else. (This memory is not all that traumatic, but it stuck with me... it's the first memory I have where gender became a big issue in my life, I guess)
Later, when I was 6, my parents built a room for me in the attic of our tiny house. One day I explored the other wing of the attic and found a pretty white box... it contained a white veil and a wreath of flowers. I just looked at it, imagining what it would look like on me, how it would feel. My mom caught me and yelled at me, she was in the midst of a terrible depression (I learned many years later) for what seemed like the first time. She asked me what I was doing with it and I lied... the first time I denied my preference for feminine things.
In elementary school I loved to hang out with the girls until I learned that was socially taboo. I was always an outcast and didn't want to be more of an outcast, so I learned to "hate girls" like the other boys. Trouble was I didn't fit in with them, so I just gave up and spent my time alone. I raised myself on books.
In my playtime, I never wanted to be the hero in my imagination... I always wanted to be the captive princess...
During puberty I tried very hard to be excited about pubes and the changes my body was going through. I figured if being a man was as exciting as all the boys seemed to think it was, maybe something inside me would change. I still spent many nights crying myself to sleep because I would never have the curves and breasts I thought I should have.
In college I came out as bisexual... but I was unhappy with all my encounters with men, because they all wanted to play with "it" or admire "it" or tell me how amazing "it" was, despite my telling them that I wanted them to pretend "it" wasn't there... In retrospect, expecting gay men to treat me like a woman in bed was a bit of a stretch, but there you go...
Also in college I had a bunch of lesbian friends, some of whom helped teach me to please a woman. It just felt natural. When a number of them went on a women's only retreat and I couldn't go, I really really hated my bio gender and was outraged that it was a reason to exclude me. (Big sign, no?)
As it became more acceptable in the media to be seen as a lesbian, I began to discover that nearly every female Hollywood star I was attracted to was a lesbian.
When I met my wife (to be, now ex) I told her that it was probably best to think of me as a mostly lesbian in a male body. I told her that I didn't need or necessarily want to use "it" to penetrate her. (Hrm... one would think *THAT* would be a sign) In fact, since the divorce I told the same thing to a number of people, potential partners or not, if the subject of sexuality and gender came up).
There were any number of others... the number of tears I shed that I could never be with a woman as a woman, with a man as a woman, my constant struggle to control my emotions, my absolute hatred of having body hair, my fascination with (and endless questions for) the trans* friends in my life... my belief that if I had a magic switch that changed my body's gender I'd flip it to F and break it off...
Yeah. I had to be in deep denial to miss all these.

Great topic.

*hug*