Hay muchísima confusión con el tema de las comisiones. El protocolo, entendiendo como tal las reglas que determinan si una transacción es válida, solamente establece que la comisión es la diferencia entre la suma de las entradas y la suma de las salidas de una transacción, pero no impone ningún tipo de comisión mínima. Una transacción con comisión 0 siempre será válida a efectos del protocolo.
Lo que ocurre es que el cliente original de Satoshi, el actual Bitcoin-qt, añadió un mecanismo antispam para evitar escenarios de ataques a la red como los que comenta Shawshank. Ese mecanismo consiste en exigir en ciertos casos una comisión mínima, que actualmente son los 0,0005 BTC que mencionas. Esa comisión mínima se aplica cuando no se cumplen tres condiciones que afectan a: 1/ el importe de los pagos (para desalentar los micropagos), 2/ el tiempo, medido en número de bloques, transcurrido desde que se recibió el dinero que se pretende enviar (para desalentar las transmisiones de dinero recién recibido) y 3/ el tamaño en bytes de la transacción (para desalentar los pagos que aglutinan muchas cantidades diferentes en las entradas o salidas). La primera de estas condiciones exige un mínimo de 0,01 BTC y es la que suele afectar a quienes intentan hacer sus primeros pagos en Bitcoin.
Lo que menciona flix de que se puede poner comisión 0 en el cliente Bitcoin-qt es cierto, pero solamente se autoriza cuando la transacción cumple esas normas antispam, en particular la de que las cantidades involucradas sean superiores a 0,01 BTC.
Además, esas reglas antispam del cliente de Satoshi han sido replicadas por los demás programas clientes y por el software de minería, con lo que se han convertido en una especie de norma
de facto de la red. La única manera que conozco de evitarla consistiría en compilar una versión modificada de un programa cliente o crear una transacción manualmente en Bitcoin-qt/bitcoind con createrawtransaction. Y no bastaría con eso, sino que tendrías también que conectarte a un nodo que ignore la norma antispam (consultar:
https://en.bitcoin.it/wiki/Free_transaction_relay_policy).
En resumen, si quieres hacer un pago de, por ejemplo, 1 BTC, lo podrás hacer con comisión 0 y seguro que entra en el siguiente bloque. Pero si estás intentando pagar una cantidad pequeña como 0,001 BTC no podrás porque ninguno de los programas cliente habituales te lo permitirá. Creo recordar que alguien alguna vez ha comentado que blockchain.info aplica una regla de comisión mínima menos restrictiva que Bitcoin-qt, pero no lo he comprobado.