You can use t
as the optional argument for the minipage
s to have vertical alignment at the top:
\documentclass{book}
\usepackage[demo]{graphicx}
\usepackage{caption}
\usepackage{subfig} % Needs subfig for this example.
\begin{document}
\begin{figure}
\begin{minipage}[t]{.48\textwidth}
\centering
\subfloat[]{\includegraphics[width=.4\linewidth]{fig1}}\\
\subfloat[]{\includegraphics[width=.4\linewidth]{fig2}}
\caption{First figure with two subfigures with very very very very long caption}
\label{fig:testa}
\end{minipage}\hfill
\begin{minipage}[t]{.48\textwidth}
\centering
\subfloat[]{\includegraphics[width=.4\linewidth]{fig3}}\\
\subfloat[]{\includegraphics[width=.4\linewidth]{fig4}}
\caption{Second figure with two subfigures}
\label{fig:testb}
\end{minipage}
\end{figure}
\end{document}

After the edit to the question: the same idea (minipage
s with appropriate vertical alignment can be used if the sucaptions have different height); now, the second optional argument for minipage
can be used to specify its height; this will guarantee that each image on the left will be placed at the same height as its corresponding image on the right:
\documentclass{book}
\usepackage[demo]{graphicx}
\usepackage{caption}
\usepackage{subfig} % Needs subfig for this example.
\begin{document}
\begin{figure}
\begin{minipage}[t]{.48\textwidth}
\centering
\begin{minipage}[t][5cm][t]{\linewidth}
\centering
\subfloat[a little longer text here; it will span several lines]{\includegraphics[width=.4\linewidth]{fig1}}
\end{minipage} \\
\begin{minipage}[t][6cm][t]{\linewidth}
\centering
\subfloat[a little longer text here; it will span several lines just for illustration in this example]{\includegraphics[width=.4\linewidth]{fig2}}
\end{minipage} \\
\begin{minipage}[t][5cm][t]{\linewidth}
\centering
\subfloat[a little longer text here; it will span several lines]{\includegraphics[width=.4\linewidth]{fig3}}
\end{minipage}
\caption{First figure with two subfigures with very very very very long caption}
\label{fig:testa}
\end{minipage}\hfill
\begin{minipage}[t]{.48\textwidth}
\centering
\begin{minipage}[t][5cm][t]{\linewidth}
\centering
\subfloat[short text]{\includegraphics[width=.4\linewidth]{fig4}}
\end{minipage} \\
\begin{minipage}[t][6cm][t]{\linewidth}
\centering
\subfloat[short text]{\includegraphics[width=.4\linewidth]{fig5}}
\end{minipage} \\
\begin{minipage}[t][5cm][t]{\linewidth}
\centering
\subfloat[short text]{\includegraphics[width=.4\linewidth]{fig6}}
\end{minipage}
\caption{Second figure with two subfigures}
\label{fig:testb}
\end{minipage}
\end{figure}
\end{document}

One could even automate the calculation for the necessary heights.
Now, it has been mentioned in a comment that the images might possibly have different heights (and widths, so this is not important); in this case, one can go with a tabular
and \captionof
from the subcaption
package; a little careful work has to be done with the counters:
\documentclass{book}
\usepackage[demo]{graphicx}
\usepackage{array}
\usepackage{subcaption}
\captionsetup[subfigure]{size=footnotesize,labelformat=parens,labelsep=space}
\newcolumntype{C}{>{\centering\arraybackslash}p{0.4\linewidth}}
\newcounter{oldfig}
\begin{document}
\begin{figure}[!ht]
\begin{tabular}{CC}
\stepcounter{figure}
\setcounter{oldfig}{\value{figure}}
\stepcounter{oldfig}
\includegraphics[width=.6\linewidth,height=1cm]{fig1}
&
\includegraphics[width=.3\linewidth,height=2cm]{fig4}
\\
\captionof{subfigure}{a little longer text here; it will span several lines}\label{sfig:11}
&
\setcounter{figure}{\value{oldfig}}
\addtocounter{subfigure}{-1}
\captionof{subfigure}{short text}\label{sfig:12}
\\
\includegraphics[width=.4\linewidth,height=1cm]{fig2}
&
\includegraphics[width=.5\linewidth,height=2cm]{fig5}
\\
\addtocounter{figure}{-1}
\captionof{subfigure}{a little longer text here; it will span several lines just for illustration in this example}\label{sfig:21}
&
\stepcounter{figure}
\stepcounter{subfigure}
\addtocounter{subfigure}{0}
\setcounter{figure}{\value{oldfig}}
\captionof{subfigure}{short text}\label{sfig:22}
\\
\includegraphics[width=.4\linewidth]{fig3}
&
\includegraphics[width=.2\linewidth,height=2.4cm]{fig6}
\\
\addtocounter{figure}{-1}
\captionof{subfigure}{a little longer text here; it will span several lines}\label{sfig:31}
&
\stepcounter{figure}
\stepcounter{subfigure}
\addtocounter{subfigure}{1}
\setcounter{figure}{\value{oldfig}}
\captionof{subfigure}{short text}\label{sfig:32}
\\
\addtocounter{figure}{-2}
\captionof{figure}{First figure with two subfigures with very very very very long caption}\label{fig:testa}
&
\captionof{figure}{second figure with short caption}\label{fig:testb}
\end{tabular}
\end{figure}
Some references to figures ~\ref{fig:testa} and \ref{fig:testb}.
Some references to subfigures ~\ref{sfig:11}, \ref{sfig:12}, \ref{sfig:21}, \ref{sfig:22}, \ref{sfig:31}, and~\ref{sfig:32}.
\end{document}
