I have feeling that dithered fills have nothing to do with Paint itself but were feature of GDI, even one pixel wide lines and such things were dithered when drawn with dithered color.
It probably got removed in Windows 2000, when GDI gained alpha channel support, as the dithering mode was specified in upper byte of 32b COLORREF, which probably got at least internally repurposed as alpha (also, alphablending dithered surfaces is not exactly sane thing to do).
I remember dithered fills being in Paintbrush itself, using Windows 3.1. My memory is you had 16 colors to work with, and to get more than that it supported dithered colors. You could have, say, a red/yellow checkerboard. The UI let you treat these like other colors: you could save them, and draw with them. When you did that, each pixel in your BMP would be set to of the 16 allowed, but the overall impression would be of more than 16 colors.
In Paintbrush you had palette of 20-ish colors, which were or were not dithered depending on whether they were displayable by your graphics adapter. (The default palette consisted of 16 default EGA/VGA colors and few dithered ones, with particularly notable burgundy-ish color that almost didn't look dithered). In the control panel you could set arbitrary 24b RGB colors for user interface elements which were dithered in exactly the same way.
Interesting thing related to this is that Windows 3.1 had significantly different default color scheme depending on what graphics driver you selected during installation. The really default color scheme was similar to OS/2 2.x (pastel colors, active window title with black text on light blue background, different background color for MDI master and slave windows) and significantly different one was used for graphics drivers with 16 or less colors (ie. the one that everybody remembers, with white text on dark blue or black background for active window title bar). Obviously the reason for this was to eliminate dithering in default color scheme.
On the other hand, this was not applied consistently. Windows 3.1 post installation tutorial essentially introduced the pastel yellow (also used in the default color scheme for MDI window background) as the "help popup color", even thought this color was dithered on VGA. Another inconsistency was that Windows 3.1 shipped with CTRL3D.DLL and some (2 or so) applications that used it. (Until Windows 10's consistent Metro-ish style I regarded CTRL3D as the most consistent UI that Windows ever had, because most applications consistently used this same UI style. The Windows 95 HIG mandated style is also nice, but it was never used consistently used by anyone, not even Microsoft itself).
I learned programming in Qbasic. My parent's computer had some "menu" launcher, which let you choose between Win 3.1 and DOS. Most games (Doom / Lemmings / Commander Keen) were DOS based. So yeah, do I need to feel old now?
