Note that Germany (as well as New Zealand and Scotland) actually has a mixed system for the Bundestag (lower, more important chamber of parliament) where roughly half the seats are determined by a district-based first past the post system and the others by a proportional system, with each voter having two votes.

The downside is that you need really complex rules to reconcile cases where the two results don't match up. This is done by adding extra seats, but can lead to edge cases where a party would actually have gotten more seats if it had recieved fewer votes.