Po rocznej przerwie powrócił na ringi K-1 w 2003 roku. W lipcu wygrał turniej K-1 World GP w Melbourne, dzięki czemu wywalczył sobie prawo startu w gali eliminacyjnej w Osace, podczas której pokonał kończącego karierę Sama Greco. Zwycięstwo to zapewniło mu udział w Finale K-1 WGP w Tokio – turnieju o mistrzostwo K-1. Odpadł w nim w ćwierćfinale, znokautowany przez późniejszego mistrza Remy'ego Bonjasky'ego.
W 2004 roku wygrał turniej Kings of Oceania 2004, pokonując m.in. Pawła Słowińskiego. Rok później zwyciężył również w Kings of Oceania 2005, uzyskując kwalifikację do turnieju K-1 World GP 2006 w Auckland (GP Oceanii), będącego eliminacją do Finału K-1 World GP 2006. W jego ćwierćfinale zmierzył się ze znanym z kontrowersyjnych zachowań Badrem Hari (przed walką doszło do bójki pomiędzy obydwoma zawodnikami). Graham przegrywał pojedynek na punkty, jednak na kilka sekund przed końcem ostatniej rundy zdołał znokautować Marokańczyka swoim markowym kopnięciem opadającym z obrotu, łamiąc mu szczękę. W półfinale spotkał się z Pawłem Słowińskim i przegrał przed czasem na skutek niskich kopnięć.
W sierpniu 2007 roku, podczas K-1 World GP w Hongkongu stoczył walkę rewanżową z Harim. Przegrał przez jednogłośną decyzję sędziów.