Edit: Ingo Karkat's answer is much better. ... I would delete this post if it wasn't accepted (which means I can't).
Here's one solution. It only searches the last 100 commands, obviously, you could change this number (History indexing starts at -1, which is the last command you typed, so the lower the number, the further is searched).
let l:i = -1
while l:i > -100
let l:cmd = histget("cmd", l:i)
if strpart(l:cmd, 0, 1) == "!"
let l:i = 1
let l:i -= 1
if l:i < 1 | echoerr "No command found" | endif
nnoremap <Leader>r :call LastCommand()<CR>