I think you miss general understanding about the Bitcoin mining problem. Try reading "Bitcoin mining in plain English", a good article trying to explain mining the easy way.
I'll answer your different questions, but some of them are quite irrelevant.
- What are these competitions/races called? Block bids? Block challenges?
I assume you mean proposals here. A block try must satisfy certain conditions to be valid. Once a miner finds a valid block, it broadcasts it through the Bitcoin network so that other miners and clients can verify it and, if it is valid, add it to their block chain.
- What software announces to all the miners that a new "block bid" is ready? In other words, how do miners know to start competing with each other?
Miners don't compete. When a miner finds a block, it announces this via a Bitcoin client. All other miners will stop their current search for a block and start to find a new block that is valid to follow the last block found by another miner.
It is important to understand that the mining problem does not get's easier to find when you try longer. Every try for a solution has an equal chance of success. It's just about making many tries. So when another miner finds a valid block, it is no problem for you to slightly change the problem you are working on because every try still has an equal chance.
- What software do miners use to compete with? bitcoind? Something else?
Miners can announce their new blocks with any client that implements the protocol. bitcoind is an obvious choice. However, many people do pooled mining, by which a mining pool gives them parts of the problem and the pool will announce new blocks when one miner finds the solution. This means that pooled miners don't need a Bitcoin client like bitcoind to mine, but only a miner program that supports pooled mining.
- Can miners write custom software the interfaces with #3 above (bitcoind or other), or is that "not allowed"?
If I understand this right, you ask if miners can write their own Bitcoin clients to announce their blocks? Of course they can. Bitcoin has an open protocol and every client that correctly implements this protocol will be accepted by the network.
- Can miners divide a "block bid" problem over multiple computers, or again, is that "not allowed"?
Of course. This is what mining pools do essentially. They distribute the problem over all miners that are registered with it. When one of them finds a block, the reward is shares among all connected miners, proportionally with their relative contribution to the problem solving.
What's allowed and what not?
To answer your question heading: everything is allowed.
You can use whatever techniques to do Bitcoin mining. It is an essential part of Bitcoins security that you cannot cheat, because everything is allowed.
However, when you don't follow the Bitcoin protocol, none of you actions will be accepted by the network. So basically, you can do everything, but there are things that you should not do, because the other people in the Bitcoin network will just ignore you when you do.