This is a great example of a business where the revenue opportunity when sold as an insurance policy may be much higher than when sold as a per-incident/per-claim service.

Reposition as lost pet insurance, with differing rates based on type of pet, age of pet, whether or not pet has a homeagain RFID implant, etc. Perhaps also offer a standard response or a premium response, where the standard includes robocalls, craigslist posting, notification to local pet shelters/SPCA/dog catcher; premium level includes posting 'lost dog' flyers in local area using craigslist-recruited 'street teams.'

Sell it through vets, a PetCo partnership, dogster.com, etc. $29/year or something affordable like that. Get a special tag and everything "this pet protected by Pet Guardian" or whatever. See also AAA, TowBoat/US, Lifelock for insurance programs that target unlikely bad things like broken down car, grounded boat, or stolen identity.

"Do you care enough about your doggie to protect him with Pet Guardian?"

Market size is big: 60% of American households own pets. If just 0.50% of these pet-owning households bought lost pet insurance @ $29/year, that's an $8mm/yr business. If you got 3% of the market, it's $50 mm/yr.