Why isn't a \vrule between \hfills centered?

Both commands should be equivalent in this case. The difference in your example comes from extra spaces inserted before and after the stretchable glues. In the \hspace version we have:

\fbox{...}     % <-- The line end here inserts an extra space token
\hspace*{\fill}\vrule\hspace*{\fill}    % <-- Same here
\fbox{...}

The case is different however in the \hfill version:

\fbox{...}            % <-- Here get a space token ...
\hfill\vrule\hfill    % <-- ... but here we don't!
\fbox{...}  

As the line ends with a control word, the following end of line character is gobbled by TeX's input processor and no space token is inserted. You can see the difference if you end the line with a pair of braces as for the \hspace version:

\fbox{...}
\hfill\vrule\hfill{}
\fbox{...}

gives

Removing all spaces by putting % at the end of all relevant lines has the same effect.

Your two inputs, when written without line breaks, look like

\fbox{...} \hfill\vrule\hfill \fbox{...}

\fbox{...} \hspace*{\fill}\vrule\hspace*{\fill} \fbox{...}

because an end-of-line is translated into a space. However, the one in the first line after \hfill gets ignored, because it follows a control sequence name. In the second example neither space gets ignored (they follow }, so they balance each other.

Always be careful when using \hfill or \hspace not to add spaces before or after them: it's not a big deal when there's just one on the line, but it is when there are two or more, as you discovered.

The correct input should be

\fbox{\parbox[t]{0.3\textwidth}{this is parbox \#1}}% <--- No end-of-line
\hfill\vrule\hfill
\fbox{\parbox[t]{0.6\textwidth}{this is parbox \#2 (using \textbackslash{}hfill)}}

\vspace{10pt}

\fbox{\parbox[t]{0.3\textwidth}{this is parbox \#1}}% <--- No end-of-line
\hspace*{\fill}\vrule\hspace*{\fill}% <--- No end-of-line
\fbox{\parbox[t]{0.6\textwidth}{this is parbox \#2 (using \textbackslash{}hspace*)}}

In the final lines it's not important, because they're followed by a blank line, so the extra space introduced by the end-of-line is removed anyway.

Of course, defining macros for this is better:

\newcommand{\cgboxes}[2]{%
  \fbox{\parbox[t]{0.3\textwidth}{#1}%
  \hfill\vrule\hfill
  \fbox{\parbox[t]{0.6\textwidth}{#2}%
  \par
}

And then you can type

\cgboxes{
  this is parbox \#1
}{
  this is parbox \#2 (using \textbackslash{}hspace*
}

or with a different style for indentation, as you prefer:

\cgboxes
 {this is parbox \#1}
 {this is parbox \#2 (using \textbackslash{}hspace*}

(other variations are possible).