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