Alex came with a DNA test... Almost everywhere I looked included one, with the exclusion of pet stores and the larger breeding facilities where it would not be cost effective to DNA birds they were going to sell anyway... Incidentally, I steered away from the latter two, not for the DNA reason, but for a myriad of other reasons. One place was the equivalent of a bird puppy mill. Yuck. I hear the RSPCA shut them down though, so hurray!
On micro-chipping. Any bird larger then a cockatiel and in good health can be safely micro-chipped. Alex is micro-chipped. It involves usually a mild anaesthetic, and the chip is inserted under the flight muscle on the side opposite to the heart. However most breeders do not bother unless it is an expensive animal (Ie Hyacinths, B+G colour morphs, and so on). I am an advocate for chipping, it returned a friends lost hyacinth once after we was stolen, but you need to weigh up the pros and cons. A chip is not visible to the eye, and the average jo who finds your bird will probably do the usual "Oh a lost bird, no I.D, I'm keeping it" thing. So chips, in conjunction with CUSTOM (not the breeder rings, they hold little way of getting a lost animal home) rings with a phone number, are the best bet on getting a bird home.
Keep in mind, chips are only as good as the vets, pet-stores and shelters that scan ALL incoming animals for them. In AUS once a animal (especially an exotic one) is reported missing, all three of the above will keep an eye out and scan all incoming animals that fit the description in hopes of finding him. Therefore I decided to chip, as if Alex was lost or stolen, I could notify all the shelters/stores/rescues ASAP and have then start scanning all incoming parrots. Like I said, this is how friends of mine managed to recover their hyacinth, and another local got her ekkie back in a similar fashion recently. It is remarkably easy for people to steal a bird, sell it to a local pet store, and get off scot free, as even if the owner recognises their bird, without a chip or other permanent ID (Open bands are not considered permanent under many laws, they can be removed, replaced and tampered with. Close bands can also be removed or tampered with) they can not prove by law it is their animal.
Chipping also carried a slight (Very minimal when done by a pro on a healthy bird) rish when anaesthetic is involved. In my case I opted for the anaesthetic after hearing the (near non-existent in our case) risks, as Alex was young and healthy, and that's an awfully big chip for a small bird!
Do I recommend it? Yes, after seeing it bring lost birds home, and in one case prove an owners ownership of a bird that would otherwise be kept by the thief. But you need to weigh up how effective the 'chipping network' (those who scan) is in your area (and country, stolen birds move a looong way) to know what the chances are or recovering a lost bird. Chips are only as good as those who scan for them.
As for the procedure itself, this is something you need to talk about with an avian vet before you do it.
As for cost? Alex was around $70, including anaesthetic and a checkup.