when i cleaned my throttle body i took it off the car and cleaned it until it was spotless as any little bits of dirt will affect it ,and have you made sure that there are no airleaks in the surrounding pipes,cant see that it would be the relays to be honest but like ive done i would change them anyhow as they are only £21 for both ,
hope this helps,carl