Does POSIX guarantee the paths to any standard utilities?

No, it doesn't, mainly for the reason that it doesn't require systems to conform by default, or to comply to only the POSIX standard (to the exclusion of any other standard).

For instance, Solaris (a certified compliant system) chose backward compatibility for its utilities in /bin, which explains why those behave in arcane ways, and provide POSIX-compliant utilities in separate locations (/usr/xpg4/bin, /usr/xpg6/bin... for different versions of the XPG (now merged into POSIX) standard, those being actually part of optional components in Solaris).

Even sh is not guaranteed to be in /bin. On Solaris, /bin/sh used to be the Bourne shell (so not POSIX compliant) until Solaris 10, while it's now ksh93 in Solaris 11 (still not fully POSIX compliant, but in practice more so than /usr/xpg4/bin/sh).

From C, you could use exec*p() and assume you're in a POSIX environment (in particular regarding the PATH environment variable).

You could also set the PATH environment variable

#define _POSIX_C_SOURCE=200809L /* before any #include */
...
confstr(_CS_PATH, buf, sizeof(buf)); /* maybe append the original
                                      * PATH if need be */
setenv("PATH", buf, 1);
exec*p("ps"...);

Or you could determine at build time the path of the POSIX utilities you want to run (bearing in mind that on some systems like GNU ones, you need more steps like setting a POSIXLY_CORRECT variable to ensure compliance).

You could also try things like:

execlp("sh", "sh", "-c", "PATH=`getconf PATH`${PATH+:$PATH};export PATH;"
                         "unset IFS;shift \"$1\";"
                         "exec ${1+\"$@\"}", "2", "1", "ps", "-A"...);

In the hope that there's a sh in $PATH, that it is Bourne-like, that there's also a getconf and that it's the one for the version of POSIX you're interested in.

Actually, I would largely answer yes. POSIX does guarantee:

1. That there is an absolute path a to standards-compliant version of each specified utility,
2. And, that you must be able to find this absolute path, and be able to execute this utility.

Though it is not necessarily guaranteed that each utility shall be in a particular directory across all systems (/bin/ps), it always guaranteed to be able to be found in the system default PATH, as an executable file.

Indeed, the only standard-specified way to do this in the standard is (in C) via unistd.h's _CS_PATH, or in the shell, via a combination of command and getconf utilities, i.e., PATH="$(command -p getconf PATH)" command -v ps must always return the unique absolute path of the POSIX-compliant ps supplied on a particular system. That is, while it is implementation-defined which paths are included in the system default PATH variable, these utilites must always be available, unique, and compliant, in one of the paths specified therein.

See: <unistd.h>, command.