I know this is locked for a time-out, but I am going to add these comments for consideration anyway.
The criteria for recognition of common-law relationships by the CF are defined at CFAO 19-41.
CFAO 19-41 -- COMMON-LAW RELATIONSHIPS
http://www.admfincs.forces.gc.ca/admfincs/subjects/cfao/019-41_e.asp
While specific documentary requirements are not identified, there is a very clear requirement to establish that the applying member and the alleged common-law spouse "have resided together as husband and wife continuously for at least one year immediately preceding the application or, if a child has been born to them, are residing together as husband and wife with the child".
Consider, for example, a service member who has been with a unit for years, who is known to his or her supervisor, whose living arrangements have been declared in personnel interviews and detailed in supervisor's staff notes, whose co-habiting partner may well be known by the supervisor. This individual has a chain of command that can vouch for the validity of their claim (see Annex A at Ref) when presented to an officer for completion of the Statutory Declaration (see Annex C at Ref).
Now, imagine a new recruit asking about common-law relationships and possible entitlements. Entitlements that could be very costly to the system when you are talking about moving spouse/family, move of F&E, and PMQ entitlements, etc. The recruit has no chain of command at the time, has no-one in the system that knows their situation, or that could possible vouch for them from within the CF.
In the latter case, a clerk at the CFRC must still take that member and his/her Statutory Declaration to one of the officers for signing. Now, there still remains a requirement to certify that the requirements of the "Stat Dec" have been met.
In order to do their job, that clerk MUST ask for documentary proof of the individual's living arrangements to establish that the year of cohabitation requirement has been met.
All this to say that the example of a serving member includes factors other than the sterile demand for "proof" and does not necessarily represent a sound example for a recruit's inquiries - what can be done within unit lines is often very different than the handling of a new recruit in a formal by-the-book fashion.