What wire is needed for a 400 Amp service between the mast and the meter?
First off, the utility generally makes the hookups at the service masthead
The first order of business is a point of clarification.  According to what I have been able to find, your utility is conventional in that they make the final connection from the service drop to the service entrance conductors coming out of the weatherhead; the 18&quot; tails are required so the linesperson can make those splices comfortably.
As to sizing...
This leaves us with mast and conduit sizing.  A 3&quot; rigid (galvanized) conduit mast is generally considered adequate for a 400A service entrance, at least from the utility service requirements I have read, as physical strength is also a factor here, not just conduit fill (although a smaller conduit wouldn't work anyway, as you'll see below, due to the need to upsize the wires).
This brings us to wire sizing, which is a bit non-intuitive as parallel wires still need to have their ampacities derated for fill as per NEC 310.15(B)(3)(a), but we also have to apply the 83% demand factor for residential services provided by 310.15(B)(7) point 1.  Furthermore, meter socket lugs aren't rated for 90°C, so we have to use the 75°C column instead.  This means your 4/0 is right out as two 4/0 wires in parallel can't even get us to 400A to begin with before we apply the derating.
So, we must upsize the wire.  While 250kcmil seems like an attractive next stop, and two 250kcmil wires in parallel can manage 410A on 75°C terminations, we have to take 20% off the top to account for the fact there are 6 wires in the conduit.  This puts us down at 328A for the parallel combination, just short of the 332A required by the 83% rule for a 400A nominal service entrance.
As a result, we find ourselves looking at 4 300kcmil Al XHHW-2 wires in the service entrance mast, 2 per leg, along with 2 250kcmil wires for the neutrals since the line neutral lug on your meter base can't take anything larger.  These give us a healthy 368A after the derate is applied, which is more than sufficient to meet our 332A requirement.  (Were this not a residential service, you'd have to provide for the full 400A nominal requirement, which'd require another size bump to paralleled 350kcmil conductors.)
You are correct that 600kcmil is the right size for using a single wire per leg for the service entrance, though -- this gives you 340A at 75°C, just enough to meet our 332A requirement.  Furthermore, it is about $0.50/ft cheaper at the time of this writing than the parallel conductors, and also takes up slightly less conduit area, albeit not enough to actually matter.  However, the larger conductors can be more difficult to pull through the conduit, which may be an issue, although the reduced surface area compared to the paralleled conductors means you have less chance of skinning the wire, all the same.