Carrier pigeons have been used succesfully in military/ espionage operations for centuries. The USN has had varying degrees of succes using dolphins in mining/ demining/ and reconnaissance ops. On the counterintel/ security side, patrol dogs are obvious choices, and in Viet Nam, geese were noted for their use as sentries.