When I set a picture as background in XP, and I set it to center or tile, it shows it centered or tiled in the preview window, but applying it occurs as if I've set it to stretch, no matter what.

This is a new issue, it never used to happen, and I am familiar with the desktop display settings, so I'm not doing anything 'wrong'. It's as simple as setting it to center and having it display as stretched.

Has anyone experienced this before or knows why it might be happening?

What SP level is your OS ? At SP3 I am not seeing any such affect.

I do see that every time I select a new background, the position choice bounces back to 'stretch' again, regardless of the previous setting or the dimensions of the new background image. The preview still behaves correctly, however, so you can re-select centre or tile and will see that in preview and apply..

Here is a link to an interesting similar question, concerning twin (or more) monitors http://www.techspot.com/vb/topic168851.html
The OP problem was caused by one monitor having a slightly different refresh rate to the other. Also check the properties of your video driver, and look for an updated driver.