I guess the issue is in Pocket PC Outlook which does not seem to support folders.
A workaround might be using categories (or whichever it is called in the English version). Both versions of Outlook support these (you can even have user-defined categories). A given contact may belong to more than one category.
You can display (or sort) your contacts by category, which somehow would provide the same service as folders.
Hope this helps