Bio-mechanically, outdoor running is supposed to be more difficult. The motion of the treadbelt in the opposite direction of your feet actually propels you forward making an equivalent speed on the treadmill easier to maintain than when running outdoors.
I have done both (track outdoors - not natural terrain which I bet will seem different). My take is, the body adapts. If you are used to running oudoors, the first few times on the treadmill seem tougher just because it is different and vice versa.
I started out on the treadmill. My first outdoor run I had to slow down on speed. Venkat, my yoga teacher and running partner had the opposite issue of adapting to a treadmill after being a track runner.
As I ran more outdoors, the difference petered out. I learned how to use my body a bit differently / more efficiently (I stay closer to the ground by elevating less and maintain a slight forward tilt - not a back rounding but the entire body in a slight forward plane when sprinting.)
After running outdoors, the feedback from the physiotherapist at the gym is that my treadmill running form has improved. He says I put less stress on my knees and feet now. Outdoor running was so hard, I had to really think/read-up about what to do to be more efficient (conserve energy by not wasting any motion) and that has become part of my running syle.
I run mainly on the treadmill now because it is more convenient and time efficient to get all my working-out done in the gym.
~* Vrinda *~