Is always possible to win King + Queen vs. King + Rook? Does every situation (except where the Queen team gets mated or the Queen is captured immediately) result in a win for the Queen team? Or can the Rook team, by perfect play, force a stalemate?
Mate is always possible, except in the cases you've outlined already. From Wikipedia:


  A queen wins against a lone rook, unless there is an immediate draw by stalemate or due to perpetual check (Nunn 2002a:49) (or if the rook or king can immediately capture the queen). ... With perfect play, in the worst winning position, the queen can win the rook or checkmate within 31 moves (Müller &amp; Lamprecht 2001:400).