Out of curiosity, did you try a paged search using the same code against AD or ADAM? I wonder if there is some sort of compatibility issue here. If the DirectorySearcher works against the MSU db, then that means that the underlying LDAP API will work too and the issue is likely either something in the code or a weird bug in S.DS.P itself.
I'm not an expert in controls, but my understand is that a control can be on the server or the client. If the control is an instruction for the server (like it would be with a paging request), it needs to be a server control. I'm not actually aware of any client side controls at all. :)
My understanding on criticality is that if the control is critical, the server must either honor it or fail the request. If it is not, then the server has the option of not processing the control if there is an issue with it for some reason.
For both of these, I think you'd get a more satifying answer by reading the LDAP spec instead. :)