Must I always call on an accredited laboratory in order to receive a document with the right logo?

If you want a calibration or verification certificate with the logo of the accrediting organisation, then you must use an accredited laboratory (Cofrac in France). Note that certain non-accredited laboratories are capable of delivering quality services.