Do you want the foot placement to adjust to the slope and stuff or to kick the boxes around or both?

It seems to me that if knew the next step (like place a normal aligned invisible footprint there) then you could use a code-routine to animation a bone structure. I've been think about that since seeing the Unity demo with walking control like this. Since bones are 100% script control able can't you write a system that works to move the character from target a to target b instead of just replaying prerecorded motions? Or use to prerecorded as a base and the use script to adjust the motion to the actual target b?

Kicking the box-> is it effective and speed friendly to c_trace from the foot a short distance -> detect the box about to be touched -> ent_create and invisible box and make it a physic object and assign it the speed and direction of the foot. Then remove after a little contact with the box. kinda like a slow physics bullet the bets the foot to the box. EDIT-> If the collision hull of the character doesn't extend below the weast then the foot should be passable and with timing the physics bullet could hit before/prefect or late. So I'm thinking you will have to check the dist traveled of the bullet and foot each frame and adjust the bullet to best sync with the foot.

EDIT ALSO-> Or could you just make invisible physics boxes around the player's foot the you code to always try and stay with the foot?