Here is a message from Antonijo Nikolic in Vienna, who has found that link searches are possible in AltaVista, although presumably using a different database than the original AltaVista:

I found out that the following search string works with AltaVista,
AlltheWeb, Yahoo Search and Lycos (Inktomi) in addition to HotBot (Inktomi):

'linkdomain:wu-wien.ac.at NOT domain:wu-wien.ac.at'

You only have to replace the operator 'link:' with 'linkdomain:'.