Your description of the "table" and the "database" are classic symptoms of a lack of Normalisation. A "table" with 20 searchable columns is not 3NF and probably not even 1NF. The best advice is to go back to first principles, and normalise the data, that will result in much narrower tables, and also fewer rows per table, but sure, mote tables. However the result also has fewer indices, per table, and overall.
And a much faster database. Fat-wide "tables" are a disaster for performance, at every level.
Partitions do not apply here, they will not ease your problem.
An id
PK is an additional column and index, a surrogate, a substitute (but not a replacement) for the real Primary Key. If you used Relational modelling techniques, that can be eliminated, at least getting down to 19 searchable indices. Any serious work on the "table" will be centred around the real PK, not the surrogate, for example, as you have seen from the restrictions re Partitions.
If you wish to discuss it, please post your DDL for the "table", plus every connected "table".
Response to Comments
The table is best thought of as "emails" but with a lot of extra fields (category/department/priority/workflow/owner) which are all properly normalised. There are a range of other variables as well including quite a lot of timestamps.
That's the very definition of a flat file, at 0NF. Unless you are using some unwritten definition of "Normalisation", it is, by your own description, not Normalised at all. It is the article one starts with before any Normalisation is commenced.
No doubt the indices will be fat-wide as well, in order to be useful for queries.
and you may not have realised yet, there is massive data duplication in that file, and Update Anomalies (when you update a column in one row, you have to update the duplicated value in the other rows), which makes your application unnecessarily complex.
You need to understand that all the Relational DBMS vendors write Relational database engines that are optimised to handle Relational databases. That means they are optimised for Normalised, not Unnormalised or Denormalised, structures.
I will not be drawn into academic arguments, and SO is question-and-answer site, not a debating site. As requested, post your DDL for the file, and all connected files, and we can definitely (a) give it some speed and (b) avoid 20+ indices (which is another common symptom of the condition). That will deal with a specific real world issue and solve it, and avoid debate.
Second, you seem to have the roles mixed up. It is you, with the problem, posting the question on SO, and it is me who has fixed hundreds of performance problems, answering. By definition the solution is outside your domain, otherwise you would have solved it, and thus you would not be posting a question; so it does not work when you tell me how to fix your problem. That would be tying me up in the same limitations that yo have, and thus ensuring that I do not fix the problem.
Also from our tests, having lots of tables to JOIN against that we need to include in the WHERE clause only makes the query slower.
Actually I tune databases for a living, and I have hundreds of tests that demonstrate joining many, smaller, tables is faster. It would be interesting to look into the test and the coding capability of the coder, but that would start a debate, so let's not do that; let's stick to the question. If you want examples of (a) serious testing which (b) proves what I have stated before being challenged, here's just one example fully documented and under scrutiny of, and corresponding test with, stalwarts in the Oracle world.
You may also be interested in this question/answer, which killed the same debate you are approaching.
Joins cost nothing. The files you join to; and the number of records joined on either side; the usefulness of an indices, that is where the cost lies. If it is another Unnormalised file (fat, wide, many optional columns), sure it will be slow.
Anyway, if you are genuinely interested in fixing your posted problem, post all your DDL and we can make it faster for you. If all you want is a yes/no answer re partitions (and to not address the causative problem), that's fine too; you already have that.