To answer your first question, you should use
\Rightarrow is far too small to give a readable result and is not spaced properly. Knuth specially defined
\iff to be used for equivalence and
\implies is the same but for implication (from amsmath). An implication is not a relation and so needs to be spaced according to how it is used. It uses a double thick space (which is about an en-space) because it's more important than a relation (the basic rule of math spacing being: the more something is important, the more there should be space around it). Compare the readability of the following formulas:
The first line uses
\Rightarrow and is completely illegible because the main part of the formula (the implication) is nearly invisible. The second line uses
\Longrightarrow and is better, but there's nothing that really sets the arrow apart from the surrounding symbols (the two inequalities relations are spaced the same way as the arrow). Finally, in the third line (which uses
\implies), the additional space clearly distinguishes the arrow from the rest and so improves the readability of the formula.
Concerning your second question, the simplest way to negate nearly any symbol whatever its length is to use
\centernot from the centernot package:
$A \centernot\implies B$
Of course, wrapping
\centernot\implies inside a
\notimplies macro like Werner did is a good idea.