Katie,
It is my opinion that to begin writing in a particular key with an awareness of the the available notes in that key, is the most stifling way to construct a melody. I'd go as far as saying, it is forced. Understanding keys and intervals is one thing but writing for me comes from the heart. It comes from listening to countless melodies that eventually live in the subconscious. I then connect with my feelings and the vast library of melodies that are stored there. I could be sitting in the most boring, mundane place but then I am somewhere else completely when I connect with my emotions and my creative spirit. Melodies come from that place. There are musical intervals and keys but I never deliberately/mechanically try to understand what I am doing. I can analyse what I have done and understand that but music is for me, exactly what I have explained and I urge anyone to follow the same practices.
Paul