diciamo che il db non è tanto normalizzato e non ho ben capito cosa vuoi ottenere, comunque questa query ti da quello che vuoi?

codice:
select a.*, b.username from messages as a inner join users as b 
on a.uid_fk = b.uid
group by b.uid

fammi sapere