First, I agree that I consider this to be an obvious feature that is missing. I actually sold my Samsung Galaxy S2 because I thought the voice activated functionality was lacking.
Beyond driving, I like voice dialing for when I'm cycling and I actually use it a fair bit walking around because I have a company-required passcode on my phone and unlocking my phone and then calling is more work than just telling the phone "call home".
As far as voice look-up systems being complex, the Motorola RAZR -released in 2003 - has voice dialing. A lot of ancient-looking Nokia's - including my wifes phone - have voice dialing. It doesn't require a lot of memory - the RAZR shipped with 16MB of RAM - and it doesn't require a lot of processing power.
Then there's the whole distraction thing... I've never understood why talking to someone over the phone using the bluetooth system in your car is more distracting than talking to someone sitting in the passengers seat or in the backseat. There are distracted driver studies for cell phone users, but are there distracted driver studies comparing that to a live person in the car? I personally have never understood how it's more distracting to talk to someone using a car's bluetooth setup than someone sitting in the backseat.
To me, voice activated dialing, and voice activated music ("play songs by Adele") are required features - for me - for a phone. I cycling ~120-180 miles per week, usually with an earbud in one ear, riding to and from work. I use voice commands all the time on my bicycle. I was really disappointed with the voice command system on the Galaxy S2, and I tried literally a dozen apps, and posted a
thread on this forum asking for suggestions, and then I ported the Galaxy S3 voice command system to my S2, wasn't happy with that either and then I gave up. I've always hoped that Google's "project majel" works really well.