Until you have at least 10 full charge/discharge cycles your battery will not have reached it's rated capacity.
With Litium-ion batteries, a 'full cycle' is when you charge/discharge the amount of it's rated capacity -- not how many times you put it to charge. Also, for this process, it is not neccesary to discharge the batery fully. You can for example charge it 20 times when it is at 50%.
The 'full discharge/charge' cycle is typically only neccesary for the internal battery measurement circuits to calibrate and it makes sense to only do it, if you see your battery meter is way off - for example, when it sits lots of time at 1% charge, or when the indicator shows very rapid non-linear discharge.
For many people with brand new iPhone 4S's it seems the 'full discharge then charge overnight' cycle only helps, because it increases the number of initical cycles to get the lithium-ion chemistry ramped up.
With regards to the need to restore. There are two issues here:
1. If your phone had iOS 5.0.1 build 9A405, as most iPhone 4S on the market today, when you did Restore in iTunes, it will load iOS 5.0.1 build 9A406. You are not offered this as an 'upgrade', because the version number is the same. I believe Apple handled things this way, because it would otherwise confuse consumers -- 9A406 loads only on iPhone 4S and if it was labeled 5.0.2 owners of other models would wonder and question what "new" is inside. Build 9A406 has new modem firmware (that control the radio chip) and apparently resolves some of the phantom Usage problems.
2. I have my theory, yet unproven, that many iPhones get some preconfiguration settings at the carrier. These settings might be suboptimal and when you Restore, they are gone, completely. That is, you get brand new, 'virgin' iPhone. They way it was designed/setup by Apple.
The actual spec of the iPhone 4S says "200 hours of standby OR 8 hours of talk time (on 3G)"