I'm not a pro rider and have never used clips on any bike. Even on your upright bike you train your legs and feet to stay where they're supposed to... if they just relaxed they'd fall off the pedals no matter which bike you're on. I've been riding my recumbent for almost 3 years now and have little interest in riding anything else, though it did take a week or two to get the "new muscle groups" factored in.
Once your legs get used to the new position, as Adam mentions, I doubt you'll get any more fatigue or whatever than you did previously. I find it less fatiguing for my legs since it takes less effort to go the same distance or speed on the 'bent (less wind resistance etc.)
The worst thing I had to get used to was the lack of ability to "stand up on the pedals" for quick jack-rabbit starts or climbing hills. That took a bit of getting used to, including getting very intimate with my derailleur shifting. The first few times you stop without gearing down for the next takeoff teach you quickly to avoid stopping without downshifting at all costs. Climbing hills, you just go through the gears more instead of standing up and pumping to get "over the top". I'm not a fast rider by any means but I find I can keep up with and occasionally pass upright riders who pass me on straight and level but run out of steam as they climb hills closely in front of me. I haven't ridden for extremely long distances (I normally drive the first part of my 32 mile commute and park the car and ride the last 7 miles to and from work) but I have ridden the entire 32 miles several times without problems of any sort keeping the feet on the pedals.
When coasting down long hills (I cannot keep up with the pedals over ~26 MPH) I have no trouble keeping the legs and feet in proper position as I rip down the hills.