Eu tentei vários regexes e ainda alguns códigos postais válidos às vezes são rejeitados.

Pesquisando na internet, na Wikipedia e no SO, só consegui encontrar soluções de validação de regex.

Existe um método de validação que não usa regex? Em qualquer idioma, eu acho que seria fácil de portar.

Suponho que o mais fácil seria comparar com um banco de dados de código postal, mas que precisaria ser mantido e atualizado periodicamente de uma fonte confiável.

Edit: Para ajudar os futuros visitantes e mantê-lo de postar mais regexes, aqui está uma regex que eu testei (a partir de 2013-04-24) para trabalhar para todos os códigos postais em Code Point (ver resposta de @Mikkel Løkke):

//PHP PCRE (it was on Wikipedia, it isn't there anymore; I might have modified it, don't remember).
$strPostalCode=preg_replace("/[\s]/", "", $strPostalCode);
$bValid=preg_match("/^(GIR 0AA)|(((A[BL]|B[ABDHLNRSTX]?|C[ABFHMORTVW]|D[ADEGHLNTY]|E[HNX]?|F[KY]|G[LUY]?|H[ADGPRSUX]|I[GMPV]|JE|K[ATWY]|L[ADELNSU]?|M[EKL]?|N[EGNPRW]?|O[LX]|P[AEHLOR]|R[GHM]|S[AEGKLMNOPRSTY]?|T[ADFNQRSW]|UB|W[ADFNRSV]|YO|ZE)[1-9]?[0-9]|((E|N|NW|SE|SW|W)1|EC[1-4]|WC[12])[A-HJKMNPR-Y]|(SW|W)([2-9]|[1-9][0-9])|EC[1-9][0-9])[0-9][ABD-HJLNP-UW-Z]{2})$/i", $strPostalCode);