Here is a dump - I don't have time to create a PR or clean this up right now.
I couldn't figure out the best order to put everything in so - todo.

Some of this is probably TMI or irrelevant to the question, but whatever - I dumped a bunch.
It's not everything, but it's a good start (hopefully).

ESLint is designed to be a stateless, single-file linter. It and the ecosystem of "API consumers" (tools that build on top of their API - IDEs, CLI tools, etc) assume this to be true and optimise based on the assumption. For most parsers (@babel/eslint-parser, vue-eslint-parser, etc) this holds true - they parse a file and forget about it, and for our parser (@typescript-eslint/parser) in non-type aware mode this also holds true. However when instructed to use type information, our parser now breaks both assumptions - it now stores stateful, cross-file information.

Type-aware linting, unfortunately, doesn't fit too well into the ESLint model as it's currently designed - so we've had to implement a number of workarounds to make it fit - we've fit a square peg into a round hole by cutting the edges of the hole. This, as you can imagine, means there are a number of edge-cases where things can get funky.

ESLint Usecases

ESLint is used by end users in one of three ways:

1. "One and done" lint runs - primarily done by using eslint folder or similar on your CLI. In this style of run each file is parsed and linted exactly once.
2. "One and done, with fixers" lint runs - primarily done using eslint folder --fix. In this style of run most files are parsed and linted exactly once, except those that have fixable lint errors that are parsed and linted up to 11 times.
3. "Continuous" runs - primarily done via IDEs. In this style of run each file can be parsed and linted 0..n times.

For a stateless, single-file system - all 3 cases can be treated the same! However for a stateful, cross-file system, each case needs its own, unique handling. For performance reasons we cache the "TypeScript Program" (ts.Program) once we've created it for a specific tsconfig because it's super expensive to create - so we are storing a cache that needs to correctly react to the state of the project.

Caching

These are the caching strategies that we can use for each usecase. Note that each usecase affords a different caching strategy!

1. "One and done" runs have a fixed cache - we can assume that the type information is constant throughout the run.
2. "One and done, with fixers" runs mostly have a fixed cache, except for those files that get fixed, but as fixers "should not break the build", we can assume that the fixed file contents won't change the types of other files.
3. "Continuous" runs are the wild wild west. The cache has to be truly reactive as anything can change at any time and any change can impact any and all types in other files.

APIs

TypeScript

TypeScript's consumer API is built around the concept of "Programs". A program stores all of the relevant information for a tsconfig and the types the files it references contain.

A Program is designed to be immutable - there's no direct way to update it. To perform updates to a Program, TS exposes another API called a "Builder Program" which allows you to inform TS of changes to the files so it can do the appropriate changes to the Program. The problem is that the builder Program API is much slower than the immutable Program API.

So where possible we want to use the immutable API for performance reasons, and only rely on the builder API when absolutely required.

ESLint's API

ESLint implements one unified API for a consumer to perform a lint run on 1..n files - the ESLint class.

There are no flags or config options that control how this class must be used by consumers. This means that ESLint cannot distinguish between the above usecases. This makes sense from ESLint's POV - why would it care when it's a stateless and single-file system; all the cases are the same to them!

This poses a problem for us though because if ESLint can't distinguish the cases, then we can't distinguish the cases and so we're left with the complex problem of "how can we implement different cache strategies without being able to tell which strategy to use?"

How ESLint calls our parser

ESLint calls our parser by calling the parseForESLint API. It tells us exactly two things: The code string being parsed and the parser options - that's it!

Note that parserOptions includes filePath which is the complete path + filename that is being parsed. Unless there was no filename provided, in which case it is set to the string '<text>'.

Problems

Cache Strategy and Codepath Selection

As mentioned above, we want to use the immutable Program API where possible as it's so much faster. We do this automatically by inferring whether or not you've run ESLint from the CLI by inspecting the environment. It's a hack, but it does work for usecase (1). Unfortunately there's no way for us to differentiate usecase (1) from (2), so we have to have a fallback to switch to the builder Program for usecase (2) so that we can update the Program after a fix is applied.
If our detection code doesn't fire, we just assume we're in usecase (3), and use the slow but safe codepaths.

Slow lint runs often occur due to incorrect usecase detection due to the user running things in ways we didn't expect / can't detect (such as custom scripts), or due to cases we haven't handled.

Disk Watchers

Ideally we'd attach filewatchers to the disk to detect when the relevant files/folders are changed. Unfortunately there's no good way to attach a watcher without creating an "open file handle"; which is a huge problem because NodeJS will not exit whilst there are open handles. Simply put - if we attach watchers and don't detach them then your CLI lint runs will never exit - meaning you have to ctrl+c them.

There is no lifecycle API built into ESLint so we can't tell when would be a good time to clean up watchers. So we can't use them! And thus our only option is to rely on what ESLint tells us - which is just going to be what file is currently being linted - and hope that is enough information.

Live File Updates

This is only a problem for usecase (3). When you make a change to file A in the IDE, the IDE extension schedules a new lint run with the contents from the editor which we use to update the Program. If you have file B that depends on the types from file A, this means that we've also implicitly recalculated the type for file B.
However, the extension controls lint runs - so we cannot trigger a new lint run on file B. This means that file B will show stale lint type-aware errors until the IDE schedules a new lint run on it.

Single-threaded vs Multi-threaded linting

The implicit update of file B's types based on changes to file A assume that both file A and B are linted in the same thread. If the aren't linted in the same thread, then updates to file A will not be updated in file B's thread, and thus file B will never have the correctly updated types for file A - which leads to incorrect lints!! The only way to fix this would be by restarting the IDE extension (or the IDE itself!)

Out-of-editor File Updates

In all IDEs it's possible that you can use the "file explorer" to move files around to different folders, or even rename files. This disk change happens outside of the editor window, and thus no IDE extension can or will tell ESLint that such a change occurred. This is a big problem for us because the Program state explicitly depends on the filesystem state!

We have some very slow fallback codepaths for this case that attempts to determine if out-of-editor changes occurred on disk, but it's not perfect code.

Fantastic, thanks Brad! I can take care of putting this up in a PR.