I am very much in favor of turning all backgrounds into a static images, that won't move with the level (assuming that was meant by "parallax background"). This makes it much easier to distinguish terrain and background (and I might even set my options to displaying background again).
As lots of styles have rather small background images (e.g. honeycomb or mineshaft), we will still need the paving function for backgrounds. Granted, with backgrounds that display a solid ground and sky at the top, this will look pretty weird if paved vertically, but for such cases we might use a rule like: "Pave up to 160 pixels vertically, and then resize once to the full height needed". As this resizing would only be done once at the very beginning (and perhaps if the player changes the zoom level, but that's rare as well), we wouldn't incur any performance issues from the resizing.