Based on the referenced AFI paragraph, can it be taken as "those services requirements placed on/within a supply", and thus applicable to variety of supplies?
Specifically, I would like to know the case of a requirement of leasing services of vehicles. We have the contractors to provide new cars and then the leasing service for 3 or 5 years start. Is this considered a "Embedded Service", and therefore exempt from adherence to this AFI?
It is difficult to make a determination without knowing the ins-and-outs of this procurement. However, the crux of your question comes down to the question of whether you are procuring true leasing services OR items of supply (via lease) with the associated services to maintain those supplies. If you determine the procurement to be a supply one, then the argument could probably be made that the embedded serivces exemption you cited may apply. However, as previously mentioned, there is not enough information available with the question and AAP isnt really the forum to make this call - that responsibility would come down to the requiring activity and contracting officer responsible for this procurement, likely in collaboration with legal and the budget officer. Be sure to document the determination, which will be paramount to determining the course of action as you proceed.
The question as to whether a lease arrangement qualifies as a supply or a service procurement is one that is often debated and has been explored through any number of contracting forums. Just within DAU's Ask-A-Professor, you might want to read the following answer(s) and consider some of the points made when making your supply vs. service decision: Home (dau.edu); Home (dau.edu)
In addition, make sure to explore the relevant regulations within FAR subpart 8.11, FAR subpart 7.4 and the AFFARS.