Formica, how about custom shoes?
This is more in response to Formica, than to the original post. A new rider would probably want to try some stock stuff first, in order to develop a sense for what she likes in a shoe:
I opened Pandora's box and got Rocket 7 road shoes for reasons similar to what is described in the posts above. Essentially, I liked the fit of most women's shoes, but the women's fit rarely came in the highest-end model. The men's models, while made from nicer materials, rarely came in half sizes below 39, and I wear a 38.5 in most men's shoes. There are a few companies that make high-end shoes in small half sizes (Time, Carnac, Vittoria, Sidi, etc), but I didn't like the fit of those shoes (for example, Sidi's toe box was a bit pointy for me.
The upside: R7s fit better than I knew was possible. Heel cup, foot bed, strap length & shoe volume are all based on my feet (formica, this would address your issues).
The soles are stiff. I really hadn't realized how much energy I was losing, particularly on climbs, until I wasn't losing it any more. It was surprising how much my climbing improved, particularly on the steep hard stuff.
Additionally, I have found that the R7s are really durable - I did an entire road season in them (something that typically wears a shoe out for me) and they fit as well as they did when I first got them. Oh, and they are extremely, ridiculously, freakishly, laugh-when-you-pick-them-up light. Almost exactly half the weight of my old Time shoes: saved A POUND over my old shoes-with cleats (I did actually weigh them).
The downside: they are EXPENSIVE. Retail for a pair of the "semi-custom" shoes is $559 - isn't that close to the cost of really nice ski boots? I wear my bike shoes almost every day... but it does hurt the wallet a bit.
So anyway, I am saving my pennies for a pair of R7 MTB shoes. I have all the same problems with my Shimano MTB shoes that I had with my old road shoes, and am confident that custom will solve them. I know that I would gladly spend $559 on a bike frame that is A POUND lighter, and if it makes me more efficient at the same time, yeay! As far as walking in them goes, I don't know yet, but Kabush and others race cross in them...
So, does anyone else out there have them in ATB form? How are they working for you?
C