"MySQL Partitioning. We decided against it because it seemed likely that it wouldn’t be much faster than our current solution."
What if you partition by HASH(user_id) instead of partitioning by month (http://dev.mysql.com/doc/refman/5.5/en/partitioning-hash.htm...)?