I think all graphics cards can support 1024x1024 textures, so for greater convenience you can cut textures in to chunks of that size. If you have edges to cover, you can cut them in to say 256x256 squares and they will use less VRAM than another 1024x1024 texture. Basically, the rule of thumb is to assume your texture is placed on the smallest square power-of-two size surface that can entirely fit your image (so 1024x50 size textures is probably a bad idea - it could use 1024x1024 size surface and waste VRAM - but some modern cards might be able to use rectangular power of two and place it on 1024x64).
But as Davioware said, you'll very quickly run out of VRAM this way. If you want low-end hardware to be able to play your game, you need to be thinking about 64mb cards, of which only 32mb may be available for your game to use (the rest used by OS, other apps etc). It's better to use tiling where you can, and add variations with scaled, rotated sprites for decoration. You can still get an interesting appearance that way, and with a much lower VRAM usage.
The tiled background object with a power-of-two size texture is a very efficient way to tile an image (it draws as fast as a single texture no matter how much you tile it). You lose that if it's not using a power-of-two size texture though.