Why are Particle Physicists still searching for the hypothetical 'Graviton'?
Of the four fundamental interactions (electromagnetism, gravity, nuclear weak force, nuclear strong force), the gravitational interaction is the only one that hasn't been successfully quantized (written as a quantum field theory). Basically, once you try to do it in the bread-and-butter way done for the other three, you start getting senseless results such as probabilities above 100% or negative probabilities. That's almost as bad as getting 1=0 in your math classes.
With string theory, there seems to be a way to get the quantization of gravity "naturally", provided you admit some weird new math conditions such as additional dimensions; it's not too high a price to pay. The problem is coming up with a way to test those predictions (and compare, with the standard model, the predictions that string theory does for other interactions); that has been a thorn on the side of string theorists. Listen to this: http://www.youtube.com/watch?v=PpQngpaHamg
The quantization of the gravitational field implies that the gravitation field has "excitation modes" which are called "gravitons"; the same way that the electromagnetic field has "excitation modes" called "photons"; and other fields have their own interaction particles.
Is there any proof or leads that give Theoretical physicists any knowlage that gravitons may exist at all?
As far as I know, there are no DIRECT experimental evidence yet that supports a quantized theory of gravity -- be it string theory or something else.
However, a good portion of theorists like string theory because it allows that quantization, not only of gravity but also of other interactions. Other physicists don't like it so much because it looks "ugly" and cumbersome (and it is a bit of a pig; but even the Standard Model isn't too cute either).
But hey, Nature doesn't have to conform to our biases...
Isnt the fact that what we consider gravity, is just curved space time,
Yes, but then how do you write the dynamics for space and time?
Classically, you write a field theory as a Lagragian -- a scalar quantity that obeys the Euler-Lagrange equation. http://en.wikipedia.org/wiki/Euler%E2%80%93Lagrange_equation The "behavior" of a system is such that its evolution minimizes the time sum (technically, the integral over time) of the Lagrangian over the "path" it follows as it unfolds. For example, if you want to know what is the trajectory a planet takes around the Sun, or that a marble makes around a bathtub, or how light bends or is reflected as it travels in transparent media -- if you have a Lagrangian describing the dynamics of the system, then the actual trajectory will be such that the sum of the values of the Lagrangian over the time you observe is the least possible (all other possible trajectories will have a Lagrangian integral that is never LESS than that one).
"Quantically", or better yet, in quantum field theory parlance, you also have an Euler-Lagrange equation; but in place of positions and velocities (which appear in the "classical" flavor of the equation) you have FIELDS (which take the part of positions) and the variation of those fields in time (which take the part of velocities). The equation look wierd, but it's still an Euler-Lagrange equation. And to calculate how the system evolves? You integrate over ALL POSSIBLE "trajectories" that it can take; the "true" trajectory is the one that minimizes the Lagrangian, and all the other trajectories interfere with themselves to cancel each other out and leaving only the "real" trajectory.
OK, that's the bread-and-butter recipe to write a quantum field theory. It works for electromagnetism (very well), it works with the nuclear weak interaction (takes some more work), it works with the nuclear strong interaction (takes some more work). You overlap the three together -- and you have a Lagrangian which is the Standard Model Lagrangian: the sum of each three Lagrangians.
Try the recipe with gravity? Boom.
Regardless of that: those theories describe the interactions of particles (through the Lagrangian) and not the behavior of spacetime. In fact, in the classical lagrangians you write the E-L equation as derivatives relative to those quantities which you want to "bend", space (positions) and time. How are you supposed to describe a dynamics of those coordinates themselves?! It's like trying to lift yourself by pulling on your ankles... I don't see how it might be done!