I created a Drupal 6 module, and in it I implemented hook_block(). I set up the block to appear in a certain region, and hook_block acted like a blockhead. The block consistently appeared in the Disabled list.
If an example of creating a block in a module would be helpful, please comment, and I'll add a brief tutorial. That aside, I'll point out what the documentation currently fails to, that the 'region' setting has an effect ONLY the first time the block is encountered.
That is, if you test your code with the block and no region specified, or a different region specified, and then add or change the region, the block entry will already exist in the database, and your region setting will have no effect unless and until you delete that row in the block table.