The cleat does not have to be extended out from the sole/tread of the shoe; the critical part is space AROUND the cleat, so it has room to interface with the loops on the pedal.

I have a pair of Sette hiker-style shoes that are for cold weather; I had to shave 6mm away from each side of the cleat to get them to click in AT ALL. But once I did, they worked perfectly.