The men, two from the Cambridge area and two from the Hove area, have been questioned and released on police bail.
The police also seized a large number of computer records and files from residential and business premises in both areas.
Senior investigating officer Chief Inspector Colin Cowan advised that the matter had been forwarded to the police by the premium rate regulator ICSTIS, which has already dealt with a large number of complaints about the company concerned.
"We endorse ICSTIS' advice and urge customers of the phone companies to be wary of unexpected messages where, to claim their prize, they have to make a call at premium rate," he said.