First of all, keep in mind that group policies that are applied will apply themselves in the most restricted manner, unless you disable policy propogation from above. The easiest thing to do may be to leave the default domain policy as it was defaulted with very little set. You don't necessarily have to put the users in different OUs because even if "10 character strong" users get the "4 character not strong" GPO, as long as the "10 character strong" policy is being applied to them, that's what they will use because it's the most restrictive. However, keeping in different containers with the GPOs separated may be easier to manage and keep track of.
Now, this should be a simple thing, but I will go ahead and ask anyway. When you set the GPOs for each type of user, did you go into the security tab for the Group Policy and make sure the users show up in the security window and that the Apply Policy check box is checked. The best thing to do is add the users to a corresponding group, add that group to the security tab of the GPO and then make sure Apply Policy is checked. Otherwise, you will get the default domain policy. So you may want to create a group that's called "Strong Security Group", add all the "10 character strong" users to it, then put it in the corresponding GPO in the security tab and check the Apply Policy check box on that group name. Hopefully this helps. Sorry for the novel.
