In the unconditionally reliable message transmission (URMT) problem, two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed graph. S has a message that he wishes to send to R; the challenge is to design a protocol such that after exchanging messages as per the protocol, the receiver R should correctly obtain S's message with arbitrarily small error probability 6, in spite of the influence of a Byzantine adversary that may actively corrupt up to t nodes in the network (we denote such a URMT protocol as (t, (1 - δ))- reliable). While it is known that (2t + 1) vertex disjoint directed paths from S to R are necessary and sufficient for (t, l)-reliable URMT (that is with zero error probability), we prove that a strictly weaker condition, which we define and denote as (2t, t)-special-connectivity, together with just (t+1) vertex disjoint directed paths from S to R, is necessary and sufficient for (t, (1- δ))-reliable URMT with arbitrarily small (but non-zero) error probability, δ Thus, we demonstrate the power of randomization in the context of reliable message transmission. In fact, for any positive integer k > 0, we show that there always exists a digraph Gk such that (k, l)-reliable URMT is impossible over Gk whereas there exists a (2k, (1 - δ))-reliable URMT protocol, δ > 0 in Gk In a digraph G on which (t,(l - δ))-reliable URMT is possible, an edge is called critical if the deletion of that edge renders (t,(l - δ))-reliable URMT impossible. We give an example of a digraph G on n vertices such that G has Ω(n2) critical edges. This is quite baffling since no such graph exists for the case of perfect reliable message transmission (or equivalently (t, l)-reliable URMT) or when the underlying graph is undirected. Such is the anomalous behavior of URMT protocols (when "randomness meet directedness") that it makes it extremely hard to design efficient protocols over arbitrary digraphs. However, if URMT is possible between every pair of vertices in the network, then we present efficient protocols for the same.