Most glues *when dried* are fairly inert. Its when they are wet that causes
the problems. Since the fuzzy thing is going to get *alot* of attention, you
need a glue that is going to dry waterproof and one that can take a fair bit
of damage. tehrefore you want a flexible glue rather than one that dries
hard & brittle. Superglue would be very bad for this job, as its is
incredibly brittle when dry. Elmer's glue sticks, if they are what I think
they are, will be pretty darn useless. Standard PVA craft glue might work
OK, as long as it dries waterproof (check first, becaus eyou don't want it
decaying inthe presence of cat spit).

I don't know what your tacky glue is, but if you've used it for crafts
before and it works on fabric (I assume thats what the fuzzy part is), that
should probably be fine as its flexible and rubbery and will be able to take
a fair degree of beating up before breaking - but the one I'd personally
recommend is the hot glue gun. Tahts already pretty impervious to water and
its very unlikely to get hot enough to come undone in a cat's mouth.

Do a test run on something similar, let it dry for the required length of
time, then soak it in body temperature water for about half an hour (or the
maximum exposure time to cat spit). If the glue changes in any way (softens,
goes milky etc) then don't use it.

HTH

Vicky