I used to do this with CD covers and such a lot... If I can remember my steps, I'll try them on the background and see how it works...
What resolution do you scan them at? One of the best ways to de-screen is to scan at a really high resolution (1200 or 2400 dpi), then apply some de-screen techniques, and re-size the image to 600 or 300 dpi equivalent if you don't need the giant images. The only way to really remove them is to lightly blur the image to force them to blend (ultimately, that's what descreeners are doing, but with algorithms tuned to the print patterns and such), which causes the softness you were noticing. But if you do that at something at least twice the resolution you want in the end, when you re-size it, the softness goes away for the most part...
1) Scans must be 400dpi or larger. If scanning in at 400dpi the "Descreen" or "Magazine" setting on your scanner software must be enabled.
2) Scans at 600dpi or above may or may not use the Descreen setting. If your scanner does not have Descreen as an option, you must scan at 600dpi or above.
Method: Scan at 600 dpi (no color correction) Appy color profile Apply Descreen 4.0 filter ($20 for the home version) resize to 300 dpi using "bicubic sharper" Fix damage with rubber stamp tool save as png (large but better than tiff while still being lossless).
Note for archival purposes 300 dpi makes sense as the halftone screen frequency is 145lpi therefore 300dpi is just over twice the screen resolution. The res nees to be more that the halftone resolution because of the non-halftone parts of the image (playstation logos/ text).
