Не знаю как в C++, но в чистом C "inline" -- это лишь рекомендация компилятору встраивать эти функции. Компилятор часто игнорирует эту рекомендацию (когда функция больше 1-2 строк). Единственный способ реально инлайнить функции, который я знаю, -- это макросы (#define). Даже attribute((always_inline)) на помогает, он просто говорит сохранять смысл inline (рекомендация на встраивание) при отключенных оптимизациях (-O0).

Смотрим http://en.wikipedia.org/wiki/Inline_function :

The compiler may ignore the programmer’s attempt to inline a function, mainly if it is particularly large.

Например вот код:

#include <stdio.h>
#include <stdlib.h>
inline int f1(int a)
{
    return a + 1;
}
inline int f2(int a)
{
    int i;
    for (i = 0; i < 10; ++i) {
        if (a < 5)
            a += 2;
        else
            a += 3;
    }
    printf("f2 done\n");
    return a;
}
int main(void)
{
    int x = 5;
    x = f1(x);
    x = f2(x);
    printf("x = %d\n", x);
    return EXIT_SUCCESS;
}

Компилируем и смотрим какие функции заинлайнились, а какие нет:

$ gcc -Wall -O2 main.c
$ objdump -DCS a.out | less

Видем следующую картину:

0000000000400450 <main>:
  400454:       bf 06 00 00 00          mov    $0x6,Мi
  400459:       e8 22 01 00 00          callq  400580 <f2>
  ...

Т.е. компилятор вообще соптимизировал вызов f1(), на этапе компиляции выполнив "5+1=6", а вот f2() уже не инлайнил и она действительно вызывается.

Вывод: проверяйте через objdump, какие функции заинлайнились, а какие нет. Соответственно те, которые не заинлайнились, gprof может видеть.
Вывод 2: если реально нужно инлайнить, попробуйте always_inline, а есть не поможет, то используйте макросы через #define

А еще хотелось бы покритиковать вашу функцию :) Которая RC5_GetByteFromWord().
1. Функция легко упрощается до формы:

inline unsigned char RC5Simple::RC5_GetByteFromWord(RC5_TWORD w, int n)
{
switch (n) {                                                                                  
case 0:
    return w & 0x000000FF;
case 1:
    return (w & 0x0000FF00) >> 8;
case 2:
    return (w & 0x00FF0000) >> 16;
case 3:
    return (w & 0xFF000000) >> 24;
default:
    return 0;
}

2. И вообще, то что вы хотите сделать, делается в одну строку :)

inline unsigned char RC5Simple::RC5_GetByteFromWord(RC5_TWORD w, int n)
{
    return (w >> (n*8)) & 0xff;
}

Тогда может и заинлайнится функция, а если нет, то:

#define GET_BYTE(w, n) ((w) >> ((n)*8) & 0xff)

Только у макроса свои недостатки, на которые можно напороться.