\Rightarrow vs. \implies, and "does not imply" symbol

To answer your first question, you should use \implies, not \Rightarrow. \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:

\documentclass{article}

\usepackage{amsmath}
\usepackage{centernot}

\begin{document}

$A \centernot\implies B$

\end{document}

Of course, wrapping \centernot\implies inside a \notimplies macro like Werner did is a good idea.

I'll answer the second part of your question, since the first seems more subjective.

You can use

\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\newcommand{\notimplies}{%
  \mathrel{{\ooalign{\hidewidth$\not\phantom{=}$\hidewidth\cr$\implies$}}}}

to represent "does not imply". This provides \notimplies that sets a relational symbol with \not overlaid \implies (technically, the other way around):

\documentclass{article}
\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\newcommand{\notimplies}{%
  \mathrel{{\ooalign{\hidewidth$\not\phantom{=}$\hidewidth\cr$\implies$}}}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\begin{document}
\[
  \X\Rightarrow\Y \quad \X\not\Rightarrow\Y \qquad
  \X\implies\Y \quad \X\notimplies\Y
\]
\end{document}

Of course, from this point the spacing can also be modified, if needed.

For a quick lesson on \ooalign, see \subseteq + \circ as a single symbol (“open subset”).

The conventions in other parts of mathematics may differ, but in logic texts, implication is virtually never written with long arrows. Implication is most commonly denoted by \rightarrow (= \to) or \supset, occasionally \Rightarrow. Long arrows (\longrightarrow and \Longrightarrow) are used for sequent arrows.