Hi Luke, welcome to the PCHF.
In regards to recovering the data - unfortunately there isn't much chance of getting windows to detect it, and the file recovery software you've already used will be your best bet to recover the files -
as long as the space on the disk they were on hasn't been over written.
It's going to be a slow proccess trying to recover your files - and not all of the files will be recoverable. But you should be able to get most of them as there's 90gb missing in windows on your drive.
As to why your your hard drive is only showing 36gb....that's an interesting one....very interesting - it's like it detected that you had the 40gb (36gb is the space available on a 40gb hdd) but formatted the wrong drive as you hope it hasn't...i've never actually seen this....
In future, i always pull out every hard drive except for the one I'm installing windows on - just "incase" as i have 2 pairs of hard drives that are identicle
Good luck and let us know how you go.