My understanding is that while lead-based paints have been implicated in some cases of propolis
"contamination", there are a number of other cases where the propolis hasn't been in contact with such
paint, and in fact where the propolis hasn't even been scraped from wooden ware (ie, collection mats
were used).
 
To add to the mystery, "high" lead levels have been detected in collection-mat propolis from hives
which were close to roadsides and  also from hives which were in remote rural areas several kms
away from roads.  There appears to be a background level of lead in propolis which has been
collected in different countries, in different areas within these countries, and using different collection
methods.
 
The levels themselves are also quite interesting.  The problem seems to be that regulations relating to
lead levels in food products are far more stringent than for medicines.  Propolis is generally used in
"medicinal" quantities, but because most countries's regulations relating to medicines are so
complicated  (especially for processing and efficacy), most manufacturers of natural remedies can't
afford the money necessary to comply.  The only alternative is to sell them as a food items.  But of
course food regulations set contaminant levels quite low because it  is generally assumed that people
will be consuming large amounts of a food product.  In fact, I have been told (but can't confirm) that the
lead levels in some types of capsules used to contain medicines are actually above those allowed by
several countries's food regulations.
 
The good news, however, is that propolis can be processed to extract out  the lead.   I understand that
this process doesn't affect any of the beneficial properties of the product.