Explanation
OGR (part of GDAL) is the library used by QGIS to access shapefiles. When OGR deletes features it does not delete them immediately, but just marks the features as deleted. Once in a while, a command called repack is executed, which creates a new file with the suffix _repack and copies all the features which are not marked as deleted to this new file. Once it finishes, the original .dbf is replaced with the _repack.dbf. It then does the same thing to the shapefile: create a new one (_packed.shp), copy all non-deleted features and eventually replace the original .shp.
It seems somewhere in this process, something failed (maybe a crash?).
Within this process, feature ids change, so I guess, that the shp (geometry) you have and the dbf (attribute table) use different feature ids for the same features, what leads to the strange behavior you experience. It seems, that one of the two files still contains (part of) the deleted features while the other one does not.
How to deal with this
Update, Nov. 2016: GDAL 2.2 ships with builtin functionality to call repack automatically whenever the file is written to the disk. So before doing anything else: check the GDAL version in the QGIS about dialog and update your GDAL (often shipped as part of QGIS) release to a recent version.
There is probably not a lot you can do about it apart from making regular backups in order not to lose more data than you can handle (you are doing that anyway, right? 😉 ). And if you find a way to reproduce this (best with a sample dataset) create a bug report.
If you experience this problem again, you can also try to create a spatial index on the shapefile. In this process, QGIS will call repack again on the shapefile, and might "repair" the shp/dbf. But this is just an unverified guess.
As mentioned by @rhm and in the comments, it may also help to rename the {xyz}_packed.{ext} file to {xyz}.{ext}. If the packed file has already been completely written and it was just the rename which failed, it is absolutely valid to do this step manually. However if the _packed file has not been completely written you may be missing information from parts of your features. So before you try this make backup copies of all the involved files.
Background information about when repack is called
Between QGIS 2.0 and 2.8 repack has been called whenever the layer was unloaded (exit QGIS, load different project...). If a feature has been deleted or a geometry changed, .shp and .dbf files with records marked as deleted have been present.
Starting with QGIS 2.10 repack is called whenever the layer is saved after an operation that has the potential to add the deleted flag to records. Therefore the files should now always be in a sane state to be processed by other applications.
What about using pyshp? I installed it with pip and what I tried below is pretty much straight out of the README:
>>> import shapefile
>>> sf = shapefile.Reader("/Users/chad/CoalOutcrops.shp")
>>> shapes = sf.shapes()
>>> len(shapes)
33732
>>> records = sf.records()
>>> len(records)
33732
>>>
Unfortunately (or maybe fortunately?) I don't have any jacked-up shapefiles to test to see if no. of shapes can != no. of records.
Wait just a minute, I do now have a jacked up shapefile thanks to Kirk's idea in the comments below. I backed up the dbf, made a copy of the entire shapefile, deleted some features, then renamed the backed-up dbf back to the original, and lo and behold, the number of shapes < number of records:
>>> sf = shapefile.Reader("/Users/chad/CoalOutcrops.shp")
>>> records = sf.records()
>>> len(records)
33732
>>> shapes = sf.shapes()
>>> len(shapes)
33721
>>>
Best Answer
An option, with the lost of the corrupted features, could be to use ogr2ogr converting your shapefile to another shapefile, with the -skipfailures option:
for further details look at this blog post from PerryGeo blog:
http://www.perrygeo.net/wordpress/?p=132