Where does the extra time between 1-2 seconds per server vs. 5-8 seconds for a threaded lookup on all servers come from? Are you doing communication between servers, or are the filesystems from all the servers available locally? If the later, is nfs or whatever actually slowing things down compared to a solution using ssh?

To "prevent" locate from recursing, filter the results looking for your specific directory.