Buy a whole car to get the block you need. I did, then wrecked what was left of the car. I made a profit!
5S responsiveness is awesome 😎

Hux billet caps - USD $525
 
https://www.huxracing.com/blank

I don't recall if the 5s caps are as hefty is the 3s ones, something about US ones differing, I don't remember exact detail as it's been 8 odd years since my research. That said there's a heap of high hp 5s builds.

I'm considering a block girdle, but I don't think it's entirely necessary.
I'll definitely get billet main caps this time around, which should prevent the same failure from happening again anyway.
The expense won't be a problem, just stressful. The only reason why the cost is more of a factor than it has been in the past, is because I bought an apartment this year and renovated it.
 

If you just replaced the caps would you still have to pull the whole thing apart to line bore it to ensure its perfectly aligned?

Mrskylighter yeah, billet main caps need clearancing, line boring, even morseo than factory caps.

Last week I talked to Advance Motor Mechanics (they'll be doing the rebuild) and I asked them to pull the engine out and strip it down when they get a chance, then they'll let me know the condition of my block, pistons, rods, etc. I realised that I shouldn't commit to anything until this happens.
If the existing internals need to be replaced anyway for whatever reason, then I'll definitely do the full 5S-GTE upgrade, but if they're still OK then I'll be able to make a choice of how far to go with it. 
 
I'm just going to put some summary notes here for my own info, but it will be beneficial to others as well. 
 
Standard 3S-GTE crank/block/pistons:
86mm bore, 86mm stroke = 1998cc displacement
 
3S-GTE crank/block/pistons (with 0.5mm overbore) (this is what I have now):
86.5mm bore, 86mm stroke = 2021cc displacement
 
Standard 5S-FE crank/block/pistons:
87mm bore, 91mm stroke = 2164cc displacement
 
5S-FE crank/block/pistons (with 0.5mm overbore):
87.5mm bore, 91mm stroke = 2189cc displacement
 
5S-FE crank, 3S-GTE block, and custom pistons to suit 5S stroke and 3S bore (with 0.5mm overbore):
86.5mm bore, 91mm stroke = 2139cc displacement
^This is a 'middle ground' with ~120cc increase in displacement due to the 5S stroke, but without the increased bore of the 5S block. 
 
NOTE:
- 3S and 5S blocks have the same height from the crank centre line to the top of the block, but 3S and 5S rods have the same centre-to-centre length of 138mm, therefore the wrist pin is 2.5mm higher in the piston when using a 5S crank. 
- 3S rods have a smaller big end diameter than 5S rods, so the crank has to be machined accordingly if using 3S rods with a 5S crank. Not a big deal. 
 
Displacement is one factor, but another is block strength.
Cost if obviously a major factor too, but its flexibility will depend on the condition of my existing internals.
 
The consensus seems to be that the 97-98 5S-FE block is the strongest. However, apart from the reinforcement of the block near the water pump, wouldn't the 5S block be weaker than the 3S block in other places due to the bigger cylinder bores?

There are a few different 5S blocks. The earlier models are not compatible with the 3S head due to the different placement of water jackets.
I use a 1993 5S block, and there is no feed point in the block for the turbo oil line.
When choosing a block, the best is the 98+ though ensure that the oil feed point is there. If you can find a 93+ with an oil feed, then that is OK too. The only difference that I can see is some additional metal around the thermostat area.
It's best to not choose a 5S block that has the balance shafts. Later model blocks don't have them.
Another thing to note is that you will no longer have piston oil squirters on the 5S. The block may be able to be modified to include them, though I didn't bother with my build.
An essential part of a 5SGTE build is ensuring that you have the right head gasket so that the water jackets align properly between the head and block. Without the right gasket, you will have overheating issues.
ATS is the only off the shelf one that I know is suitable.
The 3S flywheel needs the bolt holes to be elongated slightly to suit the 5S crank.
It's also a good idea to not use the stock OEM 3SGTE oil pump. Apparently one (not all) of the 5S variant pumps is the best one, though I haven't been able to confirm the part number. ATS sell the right one if you want to remove the risk of choosing the wrong pump. They all fit physically and will work, though some have a larger impeller and therefore more flow (not pressure).
Everything else from the 3S bolts straight onto the 5S block, including sump, oil pickup and water pump etc.
I use aftermarket rods (Eagle) and aftermarket pistons (I can't remember which brand, though I can figure it out for you if needed).

Thanks Glenn! I had come across most of that info already, but it's good to have it here now.

Whilst doing a refresh if you were to go with a later 5S block you may be able to run the later updated water pump from the ST205 part number 16100 79236 which has a different impeller wheel than that of a regular 3SGTE pump. Toyota apparently developed this style pump for the ST205 to reduce pump capitation at higher RPM and could possibly be beneficial for you when tracking the car, here are a couple of images of the impeller differences between the ST205 pump vs the regular 3SGTE pump. The regular 3SGTE pump is on the left and has a pressed metal impeller, The ST205 3SGTE pump is on the right and has a cast impeller.

 

Inside the new pump you can just see the updated impeller.