Ok. The real problem is that your order column is not really stable (or oracle sorting is unstable). It does not maintain the same sort order for different queries. However for some reasons moving this condition outside solves the problem. The queries has slightly different execution plans, which different in the details.

So, I'll reopen this issue, but as improvement with lower priority. So, for the work-around I would like to suggest to add additional column to make sorting more stable (in the case of sql fiddle example: "ID", http://sqlfiddle.com/#!4/f066c/5)

Some issue with sqlfiddle is stopping me from including the correct SQL NHibernate should be generating for the test case above. Here it is:

Please reopen this

Here's the failing test case - use the following to create the table for your SQL fiddle:
CREATE TABLE A (ID INT, D VARCHAR(10));

INSERT INTO A VALUES (1, 'A');
INSERT INTO A VALUES (2, 'A');
INSERT INTO A VALUES (3, 'A');
INSERT INTO A VALUES (4, 'A');
INSERT INTO A VALUES (5, 'A');
INSERT INTO A VALUES (6, 'A');
INSERT INTO A VALUES (7, 'A');
INSERT INTO A VALUES (8, 'B');
INSERT INTO A VALUES (9, 'B');
INSERT INTO A VALUES (10, 'B');
INSERT INTO A VALUES (11, 'B');
INSERT INTO A VALUES (12, 'B');
INSERT INTO A VALUES (13, 'B');
INSERT INTO A VALUES (14, 'C');
INSERT INTO A VALUES (15, 'C');
INSERT INTO A VALUES (16, 'C');
INSERT INTO A VALUES (17, 'C');
INSERT INTO A VALUES (18, 'C');
INSERT INTO A VALUES (19, 'C');
INSERT INTO A VALUES (20, 'A');

Notice that ID==5 is repeated twice and ID==9 is missing altogether.

Please check following SQL fiddle to check that paging is correct http://sqlfiddle.com/#!4/4e416/12

Everything works as expected.

Please read this SO answer http://stackoverflow.com/a/241643/259946, as long as mentioned links (http://weblogs.asp.net/fbouma/api-s-and-production-code-shouldn-t-be-designed-by-scientists) and comments. Especially this one:

I wondered why two WHERE couldn't be combined with AND, and then found this: http://orafaq.com/wiki/ROWNUM – Mengdi Gao Dec 17 '12 at 6:09

So, here is what really happens:

1. Select ordered data

2. Wrap data into subselect (because rownum is applied before ordering)
3. Apply rownum <= 1000
3. Give rownum to the outside of query as rownum_ (because you can not do rownum > 500 at this level)
4. Apply rownum_ > 500

So, if you want to proof that I'm wrong - please contribute a failing test case.