I know you already have many comments, but Ill throw in my couple pennies, too.
I have a 1998 Chevrolet K3500 CCSB SRW with the 5.7L Vortec. When i bought it, one cat was gone and the other was hollowed out, and like you mentioned, it didn't feel like it ran right, even with all new ignition components and all maintenance up to date. I went to Black Bear Tuning a couple years ago and they suggested I delete the rear O2 sensors in the ECM and then it should run perfectly fine.
I did and the truck runs well. My truck (even with a headache rack, 6 inch lift kit, 33s, tow mirrors, and a steel front bumper) can manage just below 14 mpg on the highway and it idles smooth as butter with enough power for me.
If you live in a place where the emissions are NOT checked (so not Cali or any big city), then I would get rid of it and try to find someone that will program the computer to mute the downstream O2 sensors.
I still have the EGR and evap stuff, and the truck runs like a top for having 267k on it.