1. My assumption that 'ldapsearch' utility gives me the right result was wrong. According to rfc4515 there is no '>' or '<' comparators - at all. Thus, ldapsearch utility forms request with filter 'objectclass=*', which gives me all the entries in the given basedn. As I have almost all the entries with uidNumber in between 500 and 1000, I misunderstood the result.

I got this fact only with wireshark's help - yes, I did tcpdump on request to find it. If 'ldapsearch' can't recognize given filter, it silently forms the filter 'present, objectClass' and treating original user's filter as attribute name to search.

2. The server actually can't answer that kind of requests; to do this, you need to modify ldap schema and define attribute with proper ordering rules. The most helpful piece of text can be found here.