What files one should backup when running a pool or other Bitcoin service? There was a big problem with Bitomat at some point where that Bitcoin exchange lost its data due to some data being lost. To prevent such problems from occurring, what files should one backup? Which files need to be backed up only once, and which should be backed up regularly? For example, should a mining pool backup its wallet.dat often, or is once enough, as the data contained in it will never change?
You need to back up your wallet.dat regularly. If your pool uses "getwork" for generating work and later generating blocks, then each block is generated with a new crypto key. Also, when you send coins out to pay your miners, the "change" is always sent to a new address. So your bitcoind is always generating new crypto keys, and you must back them up so you don't lose any coins.

So any bitcoin service that sends coins or generates new blocks with "getwork" must back up wallet.dat regularly. A bitcoind that only receives coins can be backed up only once. A bitcoind that doesn't handle coins obviously needs no backup (rare case, but can be useful).

Apart from that, of course back up your database and anything else you don't want to lose.

Update: I just want to add that bitcoind has a pool of unused keys. It makes new keys when the pool runs out. Most of the time it just takes fresh keys from the pool - and you backed those up. So you don't have to run backups once per minute to be safe. If you want to do this the best way possible you could give bitcoind the "keypoolrefill" command (and wait for that to finish) before backing up wallet.dat. This way you always back up a full pool of unused keys, and the backup will "last" as long as possible. That is to say, it will take as long as possible before the pool runs out and bitcoind generates new keys for the pool that you don't have in the backup.

There is some info on the key pool here: https://en.bitcoin.it/wiki/Key_pool.

Update 2: I'm actually unsure if "keypoolrefill" only has an effect if you resize the keypool. If you don't change the size of the pool, I think bitcoind generates a new key for the pool each time it takes a key out of it. Someone correct that if it's wrong.