Multi-tasking Straw Hats: I think that although each SH should only have one full time job, most of them seem to have secondary jobs as well. Nami's is obviously financial. Sanji is good at tactics. Chopper communicates with animals. Zoro, a former bounty hunter, and Robin, who's been a pirate/criminal most of her life, probably know a few people and things about pirating the others (except for maybe Sanji, who was raised by Zeff).
Usopp's position, however, is really stretched. He's also the resident artist and inventor - granted his artistry has only come into major play once so far (when he drew the crew's actual Jolly Roger after Luffy made his version), but he's always inventing things and that by itself can be a full-time job. The only reason he can get away with that is because marksmanship is only necessary or needed in battle, and most of the time they're just sailing. So add on carpenter and Usopp has a rather full plate - it's almost not fair to make him do all that by himself.
Running/Not Running: Tough call. It doesn't seem like most townsfolk really pay much attention to pirates - even wanted ones - as long as they're just minding their own business or not causing them any trouble. Ace is a fairly well-known pirate, yet most people didn't recognize him in Arabasta despite his notoriety.
On that note, however, I think that the absence of bounties on crew members is going to start playing a bigger role in later story arcs. If they DO find they need to be on the run all the time, they're going to run into problems with supplies - food, clothing, tools, repair supplies, and who knows what else all eventually run out and they will need to replenish these supplies. Hence, it would be very useful to have someone without a bounty who could freely walk amongst the masses to restock their supplies. Usopp (or, if Oda continues the current "Sanji wants a bounty but doesn't ever get one" running gag, the cook) are the most likely candidates to do stuff like this (as would new members of the crew who haven't had a chance to get bounties yet).
Franky and Paulie: I would love to see both of them join, especially if they get a ship that is signifigantly larger than Going Merry. Two shipwrights might be a necessity if the ship is that big.
As far as Paulie goes, the only thing really missing for him is a tragic past (and from Franky's flashback it doesn't look like Paulie had a too terrible childhood - yet). His personality would fit in nicely with the other Straw Hats - he'd be at odds with Sanji over women, Nami would have a field day with his gambling addiction (while he complains about whatever she and Robin are wearing), and his fighting style would definitely have its fair share of uses.
And just because he lacks a past now doesn't mean we won't get one later - Nami and Robin's pasts didn't show up right away, either, or Paulie could just be the odd one out who had a normal childhood, kinda like how Robin is the odd one who asked Luffy to join instead of the normal "join my crew"/"no way!" thing that happened with everyone else.
Luffy: Wait - you had a NORMAL childhood?
Paulie: Well, I fell down the stairs and broke my arm once and that kinda sucked. . .
Nami: Paulie, it's okay - you can still be our nakama even if your childhood didn't suck. It's all right.
Paulie: . . . um, it was a lot of stairs, they were on fire, and there were rabid dogs at the bottom?
Usopp: Now you're just trying to make ME look bad.