This is exactly the way we had things set up in Fortis as well (index-wise), and we made links so that when viewing an invoice you could then bring up the check that paid it, and vice versa. Sometimes one check might pay dozens of invoices.
We had a VERY elaborate query in Fortis to link AP Invoices and Checks on invoice numbers. The query was too complex for DocuWare to handle (it does not do nested parens, etc. very well). So we did what you are describing, back-filling the check number to the invoices when the checks are cut and stored into DocuWare later on.
Are you on-premise? SQL Server? What I did is write an automated program that runs periodically and does that exact thing, back-filling chek number to the invoice. I even have Foxpro code I could provide as a sample. If you are on-premise and feel comfortable with doing SQL Server queries and then using the Platform SDK to set the check number index on invoices, it could work.
Otherwise, this issue is exactly what an Autoindex Workflow is meant to help with. It might be a module worth considering.
I am curious -- are you saying you had this automated in Fortis? What did that look like? We did not do that, we just matched on invoice number. By the way, that is another option here -- depending on how many invoices your checks might pay, you could store all those invoice numbers on the Check record, yes? That would still make searches and linking difficult, but I am not sure how you were doing the back-fill in Fortis... I never ran across any sort of auto-indexing feature in Fortis.