Files and folders deleted by windows aren't really gone. The bits are still set on the disk, but the entry in the file allocation table has been deleted. If you did a quick reformat before installing windows again it's probably all still there, since the base windows installation usually goes in the same place on the disk. However, there is a very good chance some of that data has been overwritten, since the operating system looks at it as blank space, and will put things there if it has to.
If your drive was very fragmented then the process becomes even more difficult. The first time I restored a disk it had high fragmentation and I ended up with 300 copies of one large file, none of them usable, and with no direction for how to put them back together. Though some of the better software products might be able to handle this.
So in conclusion, data recovery can be done, and there is a lot of software (some free some not) to do it, but it's not a sure thing.