How do I ensure that this query sticks to indexes?

I have a database with two tables. The one contains accounts, and the other contains over 2 million rows containing addresses and their coordinates. Obviously with such an amount of rows, any time a query runs that doesn't take full advantage of the indexes will take minutes if not hours to complete. Unfortunately that is currently the case with one of my queries:

SELECT
    addr.`Linje-ID` as lineid,
    addr.`Sluttbruker` as companyname,
    addr.`Gate` as street,
    addr.`Husnr` as housenr,
    addr.`Postnr` as zip,
    addr.`Poststed` as location,
    loc.`UX_KOORDINAT` as coord_x,
    loc.`UY_KOORDINAT` as coord_y,
    loc.`ADRESSE_ID` as addr_id

FROM
    addresses addr INNER JOIN
    locationdata loc ON
        loc.`POSTSTED` = addr.`Poststed` AND
        loc.`POST_NR` = addr.`Postnr` AND
        loc.`GATENAVN` = addr.`Gate` AND
        loc.`HUSNUMMER` = addr.`Husnr`

GROUP BY
    addr.`Linje-ID`

The locationdata table has a primary index id as well as an index defined as (POSTSTED, POST_NR, GATENAVN, HUSNUMMER). Fetching rows from the table using those columns in that order goes very quickly. The query above, however, had to be cancelled as it was taking too long (>15 minutes).

As my MySQL client (HeidiSQL) freezes while queries are performed, it's getting very tedious to force the application shut and start over for every attempt to fix thi开发者_JAVA技巧s problem, so I'm asking for help here.

Just for testing, the table "addresses" only contains one row at the moment.

Can anyone identify why this query 'never' completes?

---

This is the EXPLAIN results I was asked for http://pastebin.com/qWdQhdv5

You should copy the content and paste it into a larger container as it linebreaks.

---

EDIT: I've edited the query to reflect some of your replies. It still uses over 300 seconds where it shouldn't need 1.

---

First of all I'd remove the upper from loc.GATENAVN = UPPER(addr.Gate) since this clause is already searching in a case insensitive mode.

---

I went with subqueries instead of joins