В чём различие?

Есть ″System V style IPC″ и ″posix″ очереди сообщений. Как бы разные очереди сообщений.

Пользуйся тем, что проще.

sys/msg.h - это что?

Это msgctl, msgget, msgsnd — System V style IPC. Если у вас в системе не этого файла, возможно у вас и поддержки в ядре нет.

Самое забавное, что компилится и корректно работает.

компилится и корректно работает

Не знаю, что там у вас компилируется, но, подозреваю, что код писали не вы и это нормальная программа с Makefile, расчитанная на сборку в различных условиях. Может быть несколько вариантов: <sys/msg.h> обрамлён ″ifdef″ и не обязательно инклудится или gcc ищет не ″/usr/include″ — сам компилиятор такой, или ему при вызове указана опция ″--sysroot″ или ″-I″.