I have not tried it yet, but in .NET MF 4.2 (you'd need to update to 4.2.0 RC1 firmware), there are new Directory.EnumerateFiles(...) and Directory.EnumerateDirectories(...) static methods that should work even for large amount of entries. For more detailed information, please have a look at CodePlex issue 671 (resolved with changeset 12496).
Thanks! I'll give it a try.