Would there be space for another pair of tracks to run along the eastern side of Sandy station? Instead of having a Tamworth-style cross-shaped station, the EWR line could curve around the north of Sandy and pass over the ECML before curving round to run parallel. After running past the station with a new pair of platforms, it can then curve around and head towards Shepreth, so that it would share the existing line into Cambridge at the end. This would make it similar to Nuneaton, where most traffic stays on the line it's on but it is still possible for trains to cross between them. The grade-separation of EWR and the ECML doesn't need to be perfect, as you can have trains cross the EWR tracks on the flat so long as they don't do that on the ECML. If the tracks are properly parallel through Sandy, then going between the southbound ECML and the eastbound EWR track in either direction would just involve crossing over the westbound EWR track. The switch between the northbound ECML and the westbound EWR would just require some limited extra earthworks and tracks, with the northbound ECML to EWR just needing a curve following the inside of the angle between the two lines at the EWR overbridge and the other way just needing a similar curve from the other side then curving round to rejoin the ECML.
If the line is going to be built, then it will never be rebuilt, so they may as well do it properly. Since all EWR services would call at Sandy, there would be no great harm in having some conflicting movements on its tracks if that then avoids the need for conflicting movements on the ECML. Additionally, a design like this would be able to be staged, with the line from Bedford being reopened to the new platforms at Sandy first before the link to Cambridge is built. A simpler cross-shaped scheme wouldn't be able to do this so easily, and it would also require ECML platforms to be built and ECML services to be slowed down extra.
Over in Bedford I think the best idea is to build a Bedford South at the cross between the two lines near the A421. Stopping MML services here at an extra station would be more justified than stopping ECML services at a Sandy North station because of the park and ride connection to the wider road network. The connection to the MML can be retained and simplified and St Johns station moved to wherever is most appropriate on the reopened line out to Sandy.