It sounds as though these surprisingly very dense little feet (many bones
and connective tissue) may have not infiltrated enough with paraffin. You
did not say how long you processed them in each dehydration/clearing and
paraffin step???  We found mouse feet actually took longer to decalcify
than mouse tibia/femurs.  We learned this via x-ray decalcification
endpoint checks.  Your decalcification time and endpoint checks?  you
didn't say.   

Melt the paraffin away, then reinfiltrate longer in paraffin UNDER VACUUM
if possible. 
A couple of hours and even longer may help.
 
If the tissue appears soft or mushy when you find your holes in block,  you
can go reverse processing down to 100% alcohol, and repeat that
dehydration, then resume clearing, and infiltration with paraffin.  If the
tissue seems dry, but bone cuts, then paraffin could be a problem.

We process intact decalcified mouse feet for 1 1/2 hours (have done at 2
hours per station, 70, 80, 95 x 2, 100 x 2, xylene or Clearite 3 x 2,
paraffin x 4.  Do not use heat in dehydration/clearing, paraffin was at 58C
and use Fisher Tissue Prep 2 for bone, it is a harder paraffin to support
the hard tissue.  Other paraffins should work, however. 

A hint on decalcified, paraffin embedded bone:  If the bone appears opaque
(white, not translucent), then decalcification may be incomplete OR
adequately dehydrated (processed) OR both!  If that is the case, you should
implement decalcification endpoint determinations to insure TOTAL calcium
removal OR increase dehydration, etc.  OR both.

Also, fixation of these feet takes longer than 8 hours, we left them in NBF
for up to a week before decalcification.  

  
Gayle Callis
Veterinary Molecular Biology
Montana State University
Bozeman MT 59717-3610
406 994-4705
406 994-4303