Is it overkill to wrap all memory allocations in an application (including STL push_backs etc) with some kind of bad_alloc scope guard?

There is no codebase on Earth that does that (unless somebody finds an obscurity out there). It would be a horrid mess. The whole point of alloc-or-throw is so that you don't have to error check every allocating operation.

A program can't have "strong exception safety" anyway because IO may happen before an unhandled exception is thrown. And "basic exception safety" is supposed to be guaranteed by the OS on program termination (except intermediate data in files or whatever).

I guess the closest real world case is transactions in a database, which should be well-defined even in the case of power loss.