The iPhone search has been driving me crazy as well. Another one that always gets me is pressing a number in the recent calls list just after another call was ended.
You're absolutely right. The recent calls issue happens way too often. Nothing worse than calling your boss at 2am when you meant to call your wife or vice-versa...
I often put the phone in my pocket after a call without pressing the sleep button, so the screen stays active, causing me to unknowingly "butt dial" random numbers, sometimes talking to other people while a confused/mischievous person on the call is listening in...