Did you notice any residual gasket stuck on the bottom of the timing cover?
When new, the gasket would have covered that area, so it has to be on either the pan lip or the timing cover lip, unless it crumbled and fell away during disassembly.
Cutting a strip to replace the missing gasket is a good idea, since it will raise the timing cover properly, helping to center it around the crank radial seal, and will help fill the gap between pan and cover. If the timing cover has alignment dowels, then radial seal alignment is not such an issue.

When I did my rear main seal I buggered up the pan seal a bit, but I left it in place (to help properly locate the radial seal carrier as mentioned above). I then cleaned up the area really well with brake cleaner, and ran a bead of Permatex gasket sealer over the old seal and in the corners. Worked great for the last 100k miles. any good gasket sealer should be fine, just get it really clean.

DG