They very likely won't work though...
System restore only backs up the registry, system files and certain files from the rest of the system and when you restore it brings all the above back, if the software you removed only needs the type of file that system restore backs up then the removed software will work again, if the software needs a type of file that system restore doesn't backup then it won't work.
Basically system restore is a half hearted backup at best. (I never have it switched on as I don't like or trust it)