VPOP3 6.16 is very old and uses a version of OpenSSL which didn't support all the features of TLS 1.2. I guess it works sometimes and not others because it will depend on which particular mail server at Microsoft that it hits - I guess some servers haven't had their configuration updated so still support TLS 1.1 or more basic types of TLS 1.2
So, upgrading to the latest VPOP3 is the simplest solution. I don't know the licence details of this particular instance, but if it's a 5 user VPOP3 Basic licence, the upgrade costs £25 +VAT. You can order it online at https://www.pscs.co.uk/products/vpop3/upgrade (remember to log in to our website first to get your reseller discount)
Alternatively, you may be able to use something like STUNNEL to 'wrap' VPOP3's connections in an SSL tunnel, but that is outside the scope of our free support.