In case you haven't heard, we've added some cool new functions in the Spring '08 release to help you write more powerful validation rules.

• VLOOKUP Function: Similar to its Excel counterpart, the VLOOKUP function lets you use data in another object as a basis for validation.  For example, to validate the zip code in a contact address, you could use the VLOOKUP function in a contact validation rule to search for a match in a custom object containing a list of valid zip codes.
• ISNUMBER Function: The ISNUMBER function provides a simple way to tell if data entered in a text field only contains numbers, which is required for many types of identification numbers like credit cards and account numbers. 
• REGEX Function: Regular expressions are a powerful tool used by programmers to find patterns within bodies of text.  The REGEX function gives you access to regular expressions in your validation rules.  This may be useful to validate complex number formats, like IP addresses, country-specific postal codes or phone numbers, tax IDs, and so on.
  

Check out the Advanced Validation Rules page on successforce for more information.
 
For your reference, here are links to the function documentation in the online help.
VLOOKUP function
ISNUMBER function
REGEX function

Cheers,
Eric Bezar
Force.com product management