Reference AC 20-62E.
http://rgl.faa.gov/Regulatory_and_Guida ... 20-62E.pdf
The FAA recognizes a variety of documents for the purpose of properly identifying approved replacement parts. Many of the methods mentioned here don't meet the requirements including statements on the invoice.
And it really doesn't matter if the parts are replaced under elementary maintenance. The part still has to be approved. If you simply ignore the regulations in this instance, your airplane's C of A is out of force since you have unapproved (bogus) parts on it. No C of A, means no insurance. If your airplane is damaged during flight operations, your insurance company can bow out even of the accident had nothing to do with the bogus parts if you knowingly operate without maintaining the C of A. And the AME who signed off the work is exposing himself to all sorts of possible charges for violating 571 regulations.
If a customer insisted on providing parts and there was no certification attached, I would refuse to install them. The risk just isn't worth it and if people here are implying that the extra cost isn't warranted, then I'd like them to think about how much it costs to maintain traceability and certification to the airworthiness rules. I don't know about you "questionable" airplane owners, but I don't do very much for free. As far as "approved" goes, Aircraft Spruce can also provide their own certificate of conformance (I don't think the invoice statement can be used) and often does.
Now, you have to wonder why Aircraft Spruce won't send you the documents after the fact. Why do they need the tires back and why do they have to re-ship?? Well here's the answer:
There is a degree of vigilance that the regulator and operators expect in making sure the parts used are airworthy. That means traceability. Aircraft Spruce doesn't have to maintain traceability on parts unless they are asked to. For uncertified parts, the shelf life of the tires can be expired. They could be seconds or factory rejects that meet the requirements of the basic part number but that can't be certified. So why? Because they can't guarantee the condition of your tires. Is that what you want to install on your airplane?
Its sad but the skies over Canada are quite full of bogus parts and therefore bogus aircraft. Maintainers are as much to blame as the operators.
By the way, this is what Aircraft Spruce says on their order website:
Please note that 8130 forms are not available on all items, and a charge of $100 USD (subject to change without notice) for each line item will be added to your invoice. Products requiring 8130 forms must be special ordered and delays in shipment should be anticipated. Please check with your local authorities prior to placing an order for parts for a certificated a ircraft to see if the Aircraft Spruce Certificate of Conformance on each invoice is sufficient or if 8130 forms are required.
Welcome to the regulatory world of TC, more to do with paper than safety 
This is what AvCanada excels at- exchange of industry related experiences and advice.
