For concreteness, let's pick an NP-hard problem to talk about. Given a graph $G$, the 3-colouring problem asks: "can the vertices of $G$ be painted by three colours such that for any edge $uv$, $u$ and $v$ get different colours?" This is a decision problem --- its possible answers are "yes" or "no" --- but a "yes" answer can be certified by a proper 3-colouring.
Say you had a polynomial-time algorithm that found, for any input graph, a proper 3-colouring if one exists. Then your algorithm would solve the 3-colouring problem: it answers "yes" or "no" correctly, and even gives a nice certificate (or witness) of a "yes" answer. This would be enough to show that P=NP. It is not necessary to find all possible 3-colourings (indeed, there may be exponentially many of them).
Now, if you had some sort of "partial algorithm," which solves an NP-hard problem only for some specific instances, then this is not enough. For example, the 3-colouring problem can be easily solved for bipartite graphs, split graphs, and more. The reason for this is that the restriction of an NP-hard problem is not necessarily NP-hard.
Finally, just to elaborate on Jim's answer: many popular descriptions of NP-hard problems, like Travelling Salesman, don't sound like decision problems. But they are, really: they can be retranslated as a series of questions with yes or no answers (e.g. "does there exist a travelling salesman route of length at most $x$?").