Sorry to hear the first option didn't work, it looks like toshiba has linked the recovery partition to the BCD... that's a really clever idea.
If you have a repair disk, then that should be sufficient to run Startup Repair. Boot from the repair disk and run startup repair from there as per the tutorial I posted before. Again, you may need to run it 3 times.
On a side note, it may be worth checking how you would normally access recovery options, it should be in the documentation that came with the laptop if you have it. Normally this is on F8, I suspect the laptop was ignoring it because it couldn't find an OS to boot anyway. May be worth checking though.