It's really hard to say why this is happening without EXPLAIN ANALYZE (and even then it may not be obvious), but it very much seems like the problem with correlated columns we often have with LIMIT queries.

The optimizer simply assumes the matching rows are "uniformly" distributed, because limit is costed as linear approximation of the startup/total cost of the input node. For example, consider this made up query plan

  Limit (cost=0.0..100.0 rows=10)
  -> Index scan (cost=0.0...10000000.0 rows=1000000)
     Filter: dept_id=10

The table may have many more rows - say, 100x more. But the optimizer assumes the rows with (dept_id=10) are distributed in the index, so it can scan the first 1/100000 if the index to get the 10 rows the limits needs. So it assumes the cost is 10*(0+10000000)/1000000.

But chances are the dept_id=10 rows happen to be at the very end of the index, so the planner actually needs to scan almost the whole index, making the cost wildly incorrect.

You can verify this by looking how far the dept_id rows are in "order by created_id" results. If there are many other rows before the 10 rows you need, it's likely this.

Sadly, the optimizer is not smart enough to realize there's this risk. I agree it's an annoying robustness issue, but I don't have a good idea how to mitigate it ... I wonder what the other databases do.