just in case chris doesn't have enough options here's my tuppence worth...
assuming that the plate isn't removable or doesn't have a spare set of cleat holes which can be used (like a shimano shoe plate):
1 - get a small metal drill bit (2-3mm) and drill the centre of the bolt out
2 - use a larger drill bit to remove the bolt head (6mm or so), cleat should not pop off
3 - remaoned or bolt will be left in shoe but with a central holemaking it easier to undo with pilersof by jamming an allen key into it and turning (including the obligatory hitting with hammer here )
If you do drill out the bolts remember to keep the drill bit & bolt cool with a few squirts of GT85 or similar as you go, they do get very hot and can melt the plastic shoe sole.