Recalculating full extent of File Geodatabase feature class?

Right-click the feature class in ArcCatalog and go to the Properties. In the Feature Extent tab, click on Recalculate. And voilà!

I'm using ArcGIS 10.2.1

Compacting the Geodatabase will tidy up your spatial index

"If you frequently add and delete data, you should compact your file or personal geodatabase on a monthly basis. You should also compact a geodatabase after any large-scale change. Compacting tidies up storage by reordering records and eliminating unused space. After compacting, the data in each file can be accessed more efficiently. Compacting also reduces the size of each file—it’s possible to be able to reduce the size of a geodatabase by one-half or more."

http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Compacting_file_and_personal_geodatabases/003n0000007t000000/

Compact (Data Management)

"It is recommended to compact personal geodatabases when they become larger than 250 MB. If data entry, deletion, or general editing is frequently performed on a database, the database should be regularly compacted to ensure optimal performance."

http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000000n000000

Here is an ArcCatalog add-in for ArcGIS 10 that adds a command to update the feature class extent, likely using the same method as @Ragi's VBA code:

• Re-calculate or update extent of feature class