I think there is a simple/dump way of achieving this (which I have not tried yet on code).
- You have one background image
- You have an image with the same size as the background but painted in the colours you want the border to be painted in (referred to as "border-color" image)
- You have your regular sprites
- You have a 1-bit (or 8-bit) outline sprite for each sprite
What you do is render the game in 3 layers:
- Background at the back with 100% alpha
- The "border-color" image with 0% alpha aligned to the background
- Your sprites with their alpha on top
You also need a "hidden" layer, one that will not be rendered directly on the scene. This layer will contain the "outline" sprites (which should be aligned with the regular sprites). This layer will be in turn used as the mask of the "border-color" layer.
I got the following working on Pixelmator (something like Photoshop) real quick with sprites I found on the Internet:
The border-color image is simply the background with inverted colours.