If the raster cells are much bigger than your polygons, a straight-forward approach would be to convert your clipped raster cells (some of which are totally inside, some partially outside) to polygon using the Raster To Polygon tool, and use the Select By Location tool to select the polygons that are entirely inside (CONTAINED BY) your clip polygons. You could then leave your cells as polygons or convert back to raster using Polygon To Raster (using the extent and snap raster and cell size of your clipped raster so it will line up).
Dan's other suggestion is also a good approach -- take your clip polygons, buffer them with a negative value of half the diagonal of a cell (cellsize * 1.41 * 0.5), and clip by that polygon. If the cells are not as huge as I envisioned from your description, this would be a better approach, as zillions of cell polygons are kind of hard to work with.