W lipcu 1999 roku w Puli zmierzył się w kategorii półciężkiej z Chorwatem Igorem Ivoševiciem, którego uważano za zdecydowanego faworyta; walka zakończyła się jednak zwycięstwem Maksutaja przez znokautowanie przeciwnika. 11 grudnia tegoż roku wygrał w kategorii wagowej do 79 kg w Sarajewie na punkty z Surinamczykiem Ashwinem Balrakiem.
W 2000 roku wygrał na punkty pojedynek w kategorii wagowej do 76 kg w Prisztinie z Chorwatem Ivicą Sukošiciem. W tym samym roku w Pawii stoczył tym razem w kategorii wagowej do 79 kg walkę z Francuzem Aurélienem Duarte, nokautując go w czwartej rundzie. Maksutaj wygrał również walkę w kategorii wagowej od 83 do 86 kg z belgijskim zawodnikiem Eddym Corremansem poprzez nokaut w trzeciej rundzie.
W 2001 roku znokautował w Pawii w pierwszej rundzie Francuza Davida Ismalona, z kolei w Zagrzebiu Maksutaj stoczył zakończoną remisem walkę z Rosjaninem Mohamiedem Akmarienką. W tymże roku w Winterthur również wygrał na punkty walkę w kategorii wagowej do 91 kg z Francuzem Hubertem Lisovskim. Dzień po 74. urodzinach tajskiego króla Ramy IX, dnia 6 grudnia 2001 roku odbyła się gala bokserska, która była obserwowana na żywo w parku Sanam Luang w Bangkoku przez ponad 100 tys.