Been fighting this issue where a SQL Server 2005 instance hosted on polyserve would not allow the password policy enforcement.

Something of a fix:  http://support.microsoft.com/kb/926642/en-us