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.
So what happens under Net::LDAP. Was "1000" was actually being treated as less than "500"?
Update:: Did some testing and answered my own question. I populated a few uid fields in some sample data, then ran a few ranging queries using Net::LDAP. Seems that (under open LDAP at least), not only can you get different result via ldapsearch and Net::LDAP, but the LDAP server just silently ignores the query. No errors or other status information.
Net::LDAP::Gateway contains a sample LDAP server that can dump the packets it receives as almost-human-friendly Perl data structures. It has served me in the past to compare and validate requests made through Net::LDAP and ldapsearch and solve problems as the one you were facing.