Thanks for the links Gandalf!
I have seen the ParadoxHarbinger generator before, that's pretty sophisticated stuff if I remember the maths right. For me those kind of exercises inevitably lead to doom, so the underlying mechanics of mine are much more humble
Please feel free to put up a page on your server with generated maps, that's a really neat idea (especially considering that my generator is in such an unfriendly distribution form right now). Let me know if you need any help with the code, or if you have any useful patches.
For the record: I toyed around with more ideas on making the provinces better this past weekend but wasn't really satisfied. I will obviously post any updates I make to this thread.