Can bitcoins be split up into greater than a billion parts? I understand that, at time of writing, splitting a bitcoin into more than 10⁸ parts is not useful. However, say that in the far future enough bitcoins have been destroyed (through deleted wallets due to negligence or whatever else) that a billionth becomes too valuable for people to work with. 

I know we're a long way off from this issue yet, but just say it were to happen.

Would the bitcoin spec easily allow you to further bifurcate these coin fragments into arbitrarily small values, thereby eliminating this sort of problem?
The Bitcoin protocol doesn't allow you to easily have denominations lower than a satoshi (10^-8 bitcoins). But once there is a need and widespread agreement, it can be modified to allow it.

Destroyed bitcoins however will not have any significance as a factor contributing to this need.