The majority of Antivirus technologies use Signature based detection. Essentially a list of known viruses and their variants at a given point in time.
Signature based detection can be very effective, but cannot identify malware unless it already knows and has created a signature for this piece of malware. As a result, this detection method is not useful against unknown and newly developed variants/viruses.
If Signature databases are not updated regularly there is a very real chance of infection. Most good AV vendors will release updates every day. Some AV vendors purchase 'subscriptions' to integrate into their products instead of developing their own signatures however this delays the time needed to deploy the signatures sometimes.
Most AV's will treat suspicious files in the same way running them through different technologies including Heuristic engines. Some more advanced engines exist in certain products while others do not have these features. Again, another reason why there may be differences between products.
Additionally, some viruses are created to bypass specific anti virus engines (for example a common enterprise AV solution is McAfee) and thus will be picked up by other AV's but not McAfee specifically.
With regards to 'virus encoders', i assume you are referring to 'crypting' which is the process of encrypting/obfuscating the payload of a virus in order to bypass detection. This can be picked up by AV engines who recognize the crypting technology and flag it as suspicious, however it is possible to defeat AV engines using this technique. See here for more
I'd recommend reading through the wikipedia article here
and this link Computer Virus Stategies and Detection Methods for more understanding on this topic.