Como verificar valores do formulário em tempo real

Pessoal, estou com um grande problema: Tenho um formulário gigante no meu site e todos os campos tem verificação, ou seja, verifica e-mail, caracteres inválidos, nome, verifica se todos os campos foram digitados e assim por diante.

O Problema é o seguinte: As vezes a pessoa esquece de preencher algum campo, ou esquece algum . ou @ no email, ou sem querer digita algum caractere inválido, e na hora que clica em enviar, retorna um erro, até aqui tudo bem (para mim), mas para que preenche o formulário é terrível, por que tem que digitar tudo novamente, e muitas das vezes a pessoa desiste, e isso é péssimo pra mim.

Existe alguma função em PHP (ou qualquer outra linguagem) que faça a função de verificar diretamente o que o usuário está digitando sem precisar enviar o form?

Outra coisa, no caso do e-mail ou login, eu preciso que verifique o mysql, se o usuário existe ou não.

Eu estava verificando alguns dos grandes sites aqui, como Twitter, Formspring entre outros, e tem essa função, por exemplo: Se eu digito meu usuário e este já estiver no banco de dados deles, enquanto eu digito ele já vai dizendo se posso ou nao utilizar aquele usuário.

Tem como fazer isso?