Lord Baden Powell, the father of the world scouting movement, started giving out fleur-de-lis badges to army scouts while serving in India in 1907. It's used internationally, not just in the BSA. Most countries just have "Scouts" and don't have a gender divide.
The fleur-de-lis symbol is shown as the "scouts badge" in the origional text of scouting for boys, the book that became the foundation of the scouting movement. In the text he states that it is taken from the badge used by military scouts.
So it was certainly around in 1908, when the movements founding ideas first became public. The only earlier opportunity for it's use in a scouting sense would have been the 1907 brownsea island camp.
source: "Scouting for boys, the origional 1908 edition" by Robert Baden-Powell, with introduction and notes by Elleke Boehmer, Oxford university press, 2004