GFCI outlet count towards box volume?
do I need to recalculate the volume of the box to ensure there is actually enough room?


Short answer: No

As you found out some devices are larger than others. However, the National Electrical Code doesn't distinguish between them and every yoke mounted device counts as a double volume allowance. See Article 314.

Realistically, I would use a deep device box on every device when doing new work to allow for these kinds of devices. 

Good luck.