I looked at the site listed in your profile and it would look like to me that it is within the AV database if you look for your site by using the host:YOURDOMAINNAME.com [search.altavista.com] you will see that there is 1 page listed
I also look for the sites that link to you by searching for link:YOURDOMAINNAME.com [search.altavista.com]
It has been known that AV uses link popularity to help in your site's rankings.
There are lots of other factors that you can do to help in your rankings. I would suggest that you read the New DB results [webmasterworld.com]
thread to help you with your site optimization.
However, If the site in your profile is not the one in question then I have 1 more alternative. I took over the SEO for a client that was not In the AV database and was banned for spamming. After helping the client to redesign the site and conform to the optimization standards that AV has laid out on their BEING WELL INDEXED" [doc.altavista.com] page. I also began building on the link popularity and making sure that that AV knew about the sites that linked to it. Over a few months I began a series of e-mail, with the typical automated responses. Then I just gave up for a while.
While I was looking into the List Your Product With Us [shopping.altavista.com] for another client, an AV sales rep called me a week or so later. At that time I was very unhappy with AV's service that I was not Listing my products, and this lead us into why i was upset with AV and he then asked me to send this to him an a e-mail and the chain of events that lead to that sites banning. A few days after I sent him the e-mail the site was crawled by Scooter and poof there is was every page of the site was listed and listed very well.
Now I'm not suggesting that you try this method of getting the site listed, in fact this just might be a rare case.
All i can say is if your site was banned and you have redesigned it to conform to their algorithm then go after the link popularly and make sure that AV knows that those sites link to yours.