Why can I not use variables as prefix to a command to set environment variables?

I suspect this is the part of the sequence that's catching you:

The words that are not variable assignments or redirections are expanded (see Shell Expansions). If any words remain after expansion, the first word is taken to be the name of the command and the remaining words are the arguments

That's from the Bash reference manual in the section on Simple Command Expansion.

In the cmd=bash example, no environment variables are set, and bash processes the command line up through parameter expansion, leaving bash -c "echo hi".

In the prefix=hello=hi example, there are again no variable assignments in the first pass, so processing continues to parameter expansion, resulting in a first word of hello=hi.

Once the variable assignments have been processed, they are not re-processed during command execution.

See the processing and its results under set -x:

$ prefix=hello=hi
+ prefix=hello=hi
$ $prefix bash -c 'echo $hello'
+ hello=hi bash -c 'echo $hello'
-bash: hello=hi: command not found
$ hello=42 bash -c 'echo $hello'
+ hello=42
+ bash -c 'echo $hello'
42

For a safer variation of "variable expansion" -as- "environment variables" than eval, consider wjandrea's suggestion of env:

prefix=hello=hi
env "$prefix" bash -c 'echo "$hello"'
hi

It's not strictly a command-line variable assignment, since we're using the env utility's main function of assigning environment variables to a command, but it accomplishes the same goal. The $prefix variable is expanded during the processing of the command-line, providing the name=value to env, who passes it along to bash.

Because $prefix isn't an assignment. @Jeff has the longer explanation.

You could do a similar thing with a function instead:

$ prefix() { hello=hi "$@"; }
$ prefix bash -c 'echo "$hello"'
hi

...and you can even stack those, if you like:

$ foo() { foo=123 "$@"; }
$ bar() { bar=456 "$@"; }
$ foo bar bash -c 'echo "$bar $foo"'
456 123