Julian,
I too have being looking - my requirements are slightly different to you. My 4 year old daughter has a habit of taking her feet off the pedals of her Islabike Trailerbike, normally when I am at speed. I did find a shop in the US that stocked SPD compatible shoes down to a UK size 1 but given the price (I think it was $70 + shipping) I have decided to sacrifice a pair of normal shoes and just bolt the cleats straight through the sole.
I am sorry but I can't find the reference any more to the shop but I promise you they are out there - just keep on looking!