Improve the design of the Transaction Table

So, my question -- officially -- is what is the best way to go about tracking/reconciling payments, and charges, while still allowing for overpayments, etc.

This is the problem. There are several styles of accounting. Are you using double-entry? I would recommend learning double-entry accounting. It's complicated but it works.

Is this for an actual assignment or for learning?

Here's a system that may be easy enough to dig into to give you the concepts you need to move forward? I know the author (by way of this podcast but not personally) but I haven't looked at the codebase. I just know that it does DE accounting.

http://twit.tv/floss150

There is no substitute for benchmarking. To answer the question, I would create and populate several possible tables. Then I would expose these tables to your typical workload, and benchmark.

Including additional columns in you NCIs will slow down modifications and speed up selects. Based on frequency of both, we can choose which approach uses less resources. If a row is on average read twice per year, your conclusions might be different as compared to the case when every row is on average read twice per minute.

Besides, not all queries are born equal. If some queries must complete in certain time no matter what, then you must make sure these requirements are met. Obviously such requirement trump the common good approach described above. Only you can know the actual requirements.