In my thinking, both the start and end timestamps would be optional. If one of them was omitted, between would change to a before or an after. If both were omitted, it would return all values.
I'm still not advocating for a submitted_between, though, but a generic between that includes any behavior between the dates. Then you manually filter out the events that you don't need. It keeps the API simpler and more expandable without needing to come back later and revise it again when a new field is added.
I have no pull or say with what gets implemented. You can put the feature request here, but I haven't seen much in the way of development of API through the Community as it's hard to establish broad appeal for technical requirements like this. You might get on good terms with your CSM team and see if they can make the case.
I do know that large course issues are being looked at as I sat in on one of those discussions at Project Khaki a couple of weeks ago, but the main take-away of that group was whatever changes happen for large courses are things that need to happen for smaller courses as well. There might be some API changes that result as they work on that. Unfortunately, that priority was tied for last place with 2 others and there wasn't enough engineering resources devoted to allow development of all three. So I am not sure where this happens.
There may be some reports that can never run real-time and fetch all of the data that they need through the API and have to cache the data. But I agree it would be nice to know what has changed -- especially if you have a large course or one with lots of assignments. This is true not just of submissions but for many of the tables.