Warum wird in einer m-Spalte einer Tabelle nicht vertikal zentriert?

Doch, m wirkt in der letzten Zeile und eigentlich ist genau das das Problem, da die zusätzlichen 4ex erst unten angefügt werden und dann die Zentrierung stattfindet. Für Deinen Zweck ist daher \arraystretch alleine wie in meiner Antwort auf die andere Frage gezeigt, weit besser geeignet als m-Spalten, bzw. sind ganz normale l-Spalten besser geeignet als m-Spalten. Wenn Du auf m-Spalten bestehst, solltest Du am Ende eine dummy-Spalte anfügen:

\documentclass{article}
\usepackage{array}
\renewcommand*{\arraystretch}{1.3}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{m{2.5cm}m{2.5cm}m{4cm}m{0pt}@{}}
  \hline
  \textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
  \hline
  Implikation & $p \Rightarrow q$     & aus $p$ folgt $q$        & \\[4ex]
  Äquivalenz  & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$ & \\[4ex]
  \hline
\end{tabular}
\end{document}

oder statt \\[4ex] auf \addlinespace ausweichen:

\documentclass{article}
\usepackage{array,booktabs}
\renewcommand*{\arraystretch}{1.3}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{m{2.5cm}m{2.5cm}m{4cm}m{0pt}}
  \hline
  \textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
  \hline
  \addlinespace[4ex]
  Implikation & $p \Rightarrow q$     & aus $p$ folgt $q$        & \\
  \addlinespace[4ex]
  Äquivalenz  & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$ & \\
  \addlinespace[4ex]
  \hline
\end{tabular}
\end{document}