There are two major visual pathways that help us recognise objects: the dorsal pathway, which is all about working out where stuff is and how we might interact with it; and the ventral pathway, which is about what that stuff actually looks like. (Ungerleider & Mishkin, 1983; Goodale & Milner, 1992). Evidence from neuroimaging studies suggests that even when you don't intend to pick up or otherwise have any motor interaction with objects, your brain is still, on some level, probably working out how (e.g., Faillenot et al, 1997).
As you point out, there are a number of ways in which individual items in an array can be distinguished (shape, colour, contour, etc). I'd imagine contour would a be great way of improving identifiability: if all icons have the same contours, as on the iPhone, then from a 'preparing to grasp' perspective, they all invite identical motor preparation. However, when icons' contours vary, so must grasp preparation: in other words, you have given the brain a (motor) way of distinguishing between the icons, and one that it doesn't require much conscious attention to achieve.
The dorsal "where" pathway is also involved in spatially locating items. I agree about the positional stuff discussed above: positional info is great as a way of remembering where to look for something, but when you consider that users may have several near-identical screens' worth of apps to memorise locations for, that spatial information might get diluted (this is speculative, though; I can't point to any data beyond a general consensus that uniqueness is memorable). Also, as I think someone else has pointed out, a lot of us move our app icons around as we acquire more, or re-evaluate their usefulness, so spatial navigational cues aren't necessarily very stable over time.
If we restrict icon contours to the standard Apple round-cornered squares, it has to come down to the other, less motor-based stuff — the ventral pathway's "what" function. I'm surprised nobody's banging the 'colour' drum harder here; colour is one of the major ways that I distinguish icons on my phone while searching for them (which is why I get so messed around by lots of app developers choosing shades of blue). I agree that the Map app on the iPhone is really hard to find, and I can't help but think that's because it's not visually striking: it's almost army desert camouflage in its colour-scheme (compare that to the findability of jewel-coloured apps). I wonder if there's an evolutionary thing going on here: while we've evolved highly sophisticated visual systems that can discriminate very finely (at least, given enough expertise and processing time), getting our attention without actually having something move is much more easily achieved by giving us something unusual and brightly-coloured to look at.
Lastly, just an aside: it's interesting that you say it can take you several seconds to find the one you want: the ventral pathway is generally slower than the dorsal.
