Feel like putting this in the "system" forum (because it is on overall philosophy), but, since I am talking about Kwrite 16.08.3, I guess it belongs here.

I am specifically referring (in this case) to the practice of saving "find" and "replace" strings.

Have some things I don't want in there.
Closed all instances of Kwrite.
Edited /home/user/.kde4/share/config/kwriterc
Removed Replacement Text History
Removed Search Pattern History
Set Maximum Search History Size to zero.
Started Kwrite up again.

ARGHHHHHHHHHH! Everything is still there.
How do I get rid of these once and for all?

I just followed the steps you outlined and it cleared those histories just as you expected.
Setting the maximum search history size to zero also causes it to clear those dialogs once you hit any of the find/replace buttons (you might set it to 1 just so that it keeps what you are currently searching for).

Ubuntu 14.04, KDE 4.14.13 (from backports PPAs)

If you've recently upgraded to KDE/Plasma 5, you'll need to start looking in ~/.config (configured via the $XDG_CONFIG_HOME environment variable) instead of ~/.kde4, which may be why you aren't seeing the changes being reflected.