I don't yet know how to best share example data as I cannot share the real data publicly. For completeness, here's some more data from our system:

mysql> show global variables like '%version%';
+-------------------------+--------------------------------------------------+
| Variable_name           | Value                                            |
+-------------------------+--------------------------------------------------+
| innodb_version          | 5.6.19-67.0                                      |
| protocol_version        | 10                                               |
| slave_type_conversions  |                                                  |
| version                 | 5.6.19-67.0-log                                  |
| version_comment         | Percona Server (GPL), Release 67.0, Revision 618 |
| version_compile_machine | x86_64                                           |
| version_compile_os      | debian-linux-gnu                                 |
+-------------------------+--------------------------------------------------+

mysql> show table status like 'suggestion'\G
*************************** 1. row ***************************
           Name: suggestion
         Engine: InnoDB
        Version: 10
     Row_format: Compact
           Rows: 44442324
 Avg_row_length: 152
    Data_length: 6759219200
Max_data_length: 0
   Index_length: 5125160960
      Data_free: 7340032
 Auto_increment: NULL
    Create_time: 2014-08-27 11:08:14
    Update_time: NULL
     Check_time: NULL
      Collation: latin1_german2_ci
       Checksum: NULL
 Create_options: 
        Comment: 
1 row in set (0.01 sec)

The explains you did:

mysql> EXPLAIN SELECT obj_id, flags, data, type FROM suggestion WHERE user_id='7723036' AND type IN ('newbie', 'group') AND rejected='n' AND flags=0 ORDER BY type DESC, created DESC;
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
| id | select_type | table      | type  | possible_keys                 | key     | key_len | ref  | rows | Extra                       |
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | suggestion | range | PRIMARY,user_id,type,rejected | PRIMARY | 5       | NULL |   62 | Using where; Using filesort |
+----+-------------+------------+-------+-------------------------------+---------+---------+------+------+-----------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT obj_id, flags, data, type FROM suggestion WHERE user_id='7723036' AND type IN ('newbie', 'group') AND rejected='n' AND flags=0 ORDER BY type DESC, created DESC LIMIT 50;
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
| id | select_type | table      | type  | possible_keys                 | key  | key_len | ref  | rows     | Extra                              |
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
|  1 | SIMPLE      | suggestion | range | PRIMARY,user_id,type,rejected | type | 1       | NULL | 41129152 | Using index condition; Using where |
+----+-------------+------------+-------+-------------------------------+------+---------+------+----------+------------------------------------+
1 row in set (0.00 sec)


Excerpts from our my.cnf with all performance-related settings:

key_buffer_size         = 4095M
max_allowed_packet      = 16M
thread_cache_size       = 50
table_open_cache        = 20000
join_buffer_size        = 16M
read_buffer_size        = 12M
read_rnd_buffer_size    = 32M
sort_buffer_size        = 8M
tmp_table_size          = 512M
max_heap_table_size     = 512M
max_connections         = 2000

query_cache_limit       = 1M
query_cache_size        = 128M
query_cache_type        = 0

transaction-isolation = REPEATABLE-READ
innodb_lock_wait_timeout = 15
innodb_buffer_pool_size = 13G
innodb_log_file_size = 256M
innodb_log_buffer_size = 8M
innodb_flush_log_at_trx_commit = 2
innodb_thread_concurrency = 0
innodb_flush_method = O_DIRECT
innodb_file_per_table


I'll have a try whether I can create some test data which shows the same behaviour as our real data one of the next days.