Well, it's 10 min/level, so sticking to CL=HD gives them 20 min/day. If we keep the bonus feat Track and Survival bonus, that's probably sufficient in an urban area. I suppose I could be persuaded anywhere up to CL 6, but no higher, though.
I'm tempted to give them the ability to sniff out the trail of any creature affected by their venom, similar to how some snakes follow the scent of their venom to find prey that flee after being bitten.
Track Venom (Ex): A tatalla can follow the scent of its own venom (but not the venom of another tatalla). This allows it to track any creature poisoned by its bite as if the tatalla had the Track feat and the scent special quality, with a +10 racial bonus on its Survival checks to track by scent.
I'm afraid the locate creature approach is problematic. The spell has a long range, so an average 2 HD tatalla couldn't find a victim more than 480 feet away. A typical humanoid can exceed that distance in under a minute.
Besides, I like the "tracking venom" approach. To make it "unerring" the Track check could become an auto-success:
Venom Tracking (Su): A tatalla can unerringly track any creature it ever hit with its venomous bite. Treat this as if the tatalla has the Track feat and scent special quality, it automatically succeeds on Survival checks to track creatures it has envenomed. Venom tracking can be fooled by mislead and nondetection spells. A neutralize poison spell removes the infinitesimal traces of venom necessary for venom tracking. Venom tracking only works for the tatalla's own venom, it can not track the venom of other tatallas or poisonous creatures.
I'm not fond of the "venom tracking". Let's find a compromise on the necessary caster level for locate creature (or just make it a Su ability and set the range that way).