That's a great idea! It would only cost a few bucks to find out.
The interesting idea about the bitgrid is that you can spread the emulation across cores, as none of the cells are Turing complete. Do all of phase A, then all of phase B, repeat.
It's quite variable even in instance types, I've emailed some VPS providers asking and the response was always it's not guaranteed, you'll have to test and see.
I'm guessing there some out there, but it's not the people I have accounts with.
The interesting idea about the bitgrid is that you can spread the emulation across cores, as none of the cells are Turing complete. Do all of phase A, then all of phase B, repeat.