You should use the clip tool from the data management toolbox.
When using the tool, select your polygon as the Output Extent.
Tick the box to Use Input Features for Clipping Geometry (this becomes available when you add the polygon in the Output Extent).
Tick the box to Maintain Clipping Extent.
This will resample the raster at the clipping boundary to match the polygon boundary and will result in a raster that covers the entire polygon.
UPDATE: Your cell size is very large. There is no way cells that big will ever match up with your polygon boundary. You will either have overlap or gaps.
To match the polygon boundary, you will need to resample the raster to smaller cell size. You're trying to fit a square peg into a round hole, if that makes sense (you have big square blocks that you are trying to fit into a curved polygon boundary - you need to make the block smaller).
