My departure airport is also fully international, ENGM - Gardermoen which is the largest airport in Norway, but I agree that the reply you got suggests it is (or the controller think it is) restricted by VFR rules.
In the VFR guide to Norway it is clearly stated:
"If you like to bring your EOBT forward or
delay your flightplan, this is not a
problem.
Notify ATC or call AIS (tel. (+47) 64 81
90 00 (H24)) if you change the EOBT
more than 30 mins. either way. "
Generally Norway follows EASA rules and we have implemented most of the SERA regulations, however SERA allows for national differences in some cases.
However when checking the British VFR Guide it only covers delays not early departures.