What legally constitutes a license?

Having inherited a disorganised IT dept, I need to collate existing software licenses. Can anyone explain to me (and provide documentary evidence) of what actually constitutes a valid licence. Software which I believe we are entitled to use consistsof W95/98/2000/NT4 Srv under retail, OEM and MOLP agreements. In the case of retail and OEM is possession of the EULA evidence enough or is proof of purchase required as well. From a technical standpoint it appears to me that licencing rules (and particularly MS) are deliberately “grey”. Having approached FAST and our MOLP reseller for advice it appears that there is no concensus as to what is actually the case.