By removing some unneeded content (for those interested I will detail later what I have removed and how) from the winre.wim I have managed to get the size of the updated file down enough so that it will fit on an existing 500mb recovery partition.
Since all our machines are running indentical images / same versions (build) of Windows I therefore can deploy this same file across all the machines now without having to follow the lengthy steps on each machine, and as I have psremoting enabled across all machines I can do this all remotely sitting on my ar$£ thankfully and thanks to above without having the hassle of partition resizing etc.
So my steps from a powershell admin prompt would be roughly as below - and I can then make this into a script to run across multiple machines automatically with logging / error handling etc.
1) enter-pssession {computer_name}
2) reagentc /disable
3) Copy-Item -Path "\\server\share\winre.wim" -Destination "c:\windows\system32\Recovery\
4) reagentc /enable
5) exit
Probably not the perfect solution but it works - I can boot into the recovery environment fine, all the tools work, and it has been patched - problem resolved for now - until Microsoft throw us another curve ball.