PostgreSQL not using varchar index when ordering by primary key

My company has a pretty large PostgreSQL 9.4.5 database (we'd rather not try updating it atm as it's stable), one of the tables used to hold some sort of statistics wasn't designed well and when it grew, queries to it became slower and slower. This table is used for calculating global statistics periodically and for showing last 20 stats of a selected device.
At the moment, there is >150m rows in this table, and in the place where we pull the last 20 rows for a device, the query takes more than a minute to execute and causes a huge memory usage spike on the server.

The structure of the table is like this:

       Column        |            Type             |

---------------------+-----------------------------+
 id                  | bigint                      |
 datetime            | timestamp without time zone |
 device              | character varying(225)      |
 file                | character varying(225)      |
 duration            | character varying(225)      |

Indexes:
    "statistics_pkey" PRIMARY KEY, btree (id)
    "statistics_device_idx" btree (device)

There are a few more columns with informations, but they aren't included in any queries and hold no interesting data, mostly text.

When searching for the statistics, we select the device and the date, the query fetches 20 rows of that device that are before the selected date:

SELECT * FROM statistics WHERE device = '7329_218550' and datetime < NOW() ORDER BY id DESC LIMIT 20;

This query causes the trouble. Explain of it:

Limit  (cost=0.57..1029.06 rows=20 width=553)
  ->  Index Scan Backward using statistics_pkey on statistics  (cost=0.57..11129443.84 rows=216424 width=553)
        Filter: (((device)::text = '7329_218550'::text) AND (datetime < now()))

As you can see, the device index is not being used at all, I was surprised as it's the main column we use for filtering and it had an index.
I found out, that by just removing the ORDER BY from the query, the index is being used properly, and queries take ~0.004s which is a tremendous difference:

Limit  (cost=0.57..78.00 rows=20 width=553)
  ->  Index Scan using statistics_device_idx on statistics  (cost=0.57..837920.42 rows=216424 width=553)
        Index Cond: ((device)::text = '7329_218550'::text)
        Filter: (datetime < now())

I found out, that using the datetime field for ordering (since we want the last 20 rows anyway) and although the explain is more complex, it actually USES the index again! Which surprised me even more, because ordering by a primary key should be better than by some time field:

Limit  (cost=669994.92..669994.97 rows=20 width=553)
  ->  Sort  (cost=669994.92..670535.98 rows=216424 width=553)
        Sort Key: datetime
        ->  Bitmap Heap Scan on statistics  (cost=4138.01..664235.95 rows=216424 width=553)
              Recheck Cond: ((device)::text = '7329_218550'::text)
              Filter: (datetime < now())
              ->  Bitmap Index Scan on statistics_device_idx  (cost=0.00..4083.91 rows=216445 width=0)
                    Index Cond: ((device)::text = '7329_218550'::text)

Queries ordering by datetime are executing in ~3.5s, which is a lot more than without ordering, but it's still much better than ordering by the primary key.

Why is it like that, and is there any way to use the index properly and keep the ordering?