The procedure my shop offer to our customers is usually as follows:
A customer purchases a Nokia Handset from us (ie not from another store that sells Nokia phones) but there is something wrong after a couple of months. It brought back to us and is sent away for repair under warranty, and the customer is given a temporary phone to use in the meantime (a cheap 1112 handset so it wont get stolen). After 2 weeks the handset is usually fixed and returned to the customer, all on our records.
If the customer experiences the same fault after this initial repair then they are advised to bring it back to our shop and we organise a repair again. The repair staff would be told that it is the 2nd time away and is considered a priority case. When it is returned the customer gets the handset back.
If in the unusual circumstance the handset is still faulty then the case is taken up with the area manager/director of retail for our company. The outcome is assessed on a case by case scenario but usually it is arranged for the handset to either be returned and replaced at the repair centre or we would do a handset exchange for the same model as a gesture of good will.
This is by no means a legally enforced procedure and is only a discription of what MY company does.
I would consider speaking to the retailler you purchased the handset from and expain the situation to them. They may have a similar process to my company, but you cannot guarantee it. If you purchased your handset with a contract, you may be able to obtain legal advice to terminate the contract through your service provider not supplying you with a working handset, which hinders your ability to use the contents of the contract (ie texts and calls).
Unfortunately due to the nature of all electronic items, the warranty is usually mistaken as a right to exhange or refund at any given point - of which it is neither. As harsh as it may sound, you should be lucky that you are able to get most handset faults reapired for free because of this warranty.
I am sorry you are having a bad time, but I believe Nokia have an excelent level of customer service from my experience and I am sure they have done everything they can do to provide you with a solution whilst retaining the esscence that they are a profitable organisation, not a charity, and is their right to do so.