There are a variety of ways a trial application could do this, the registry being only one. Let us assume it does use the registry. System Restore does not restore the entire registry but only portions of it. All the application has to do is store some obscure value in some unsuspected location. Someone could be looking at it and never recognize it for what it was. If the application installer found this value it would know the application had been previously installed.
One such location would be the profile of one of the built in accounts. This would not be touched by System Restore and is easily accessed. Developers are aware of how System Restore works and would use a location it would not reverse. And developers tend to be very resourceful. Any competent developer could think of several other methods in little time. Obviously none of this would be documented.