Preservation is quite good at many Utah prehistoric sites, and lots of
fiber sandals have been recovered.  The Edge of the Cedars Museum in
Blanding, Utah has some curated.  I don't know if their collection
contains moccasins or sandals with leather parts.  You could call their
Curator of Exhibits, Deborah Stevens, at 435-678-2238, and inquire.
 
You could also check with the SHPO.  Try 801-533-3500 and ask for Kevin
Jones or Jim Dykman.
 
*Lee Bennett
*Bennett Management Services
*Monticello, Utah