A leaked Nokia presentation about N-Gage in late 2006 did mention vouchers as a possible payment method but nothing was heard of that since. It does imply they've been thinking about it though, and if there's demand for it perhaps they will reconsider implementing it.
As mentioned above, from Nokia's point of view maybe the best idea would be a single combined "Nokia Voucher", where you could use it to add credit to any of Nokia's online services. That would reduce the costs of making each voucher, widen the audience for each service to people without credit cards, and promote the full range of Nokia services all at the same time. Such vouchers could also be used with any future services Nokia cares to launch.
