You need to declare the escape sequences sent by your usual terminals in your ~/.vimrc. In theory, escape sequences depend on the terminal. In practice, if an escape sequence corresponds to a certain key on a given terminal, other terminals either send it for the same key or don't send it at all, so you can just pile on the definitions and not worry about conflicts.
To find out what escape sequence a key sends, enter insert mode and press Ctrl+V followed by the key. This inserts the escape sequence literally.
Put directives like these in your ~/.vimrc (using the escape sequences that you've observed):
function Allmap(mapping)
execute 'map' a:mapping
execute 'map!' a:mapping
endfunction
call Allmap(' <ESC>[A <Up>')
call Allmap(' <ESC>[B <Down>')
call Allmap(' <ESC>[C <Right>')
call Allmap(' <ESC>[D <Left>')
call Allmap(' <ESC>[F <End>')
call Allmap(' <ESC>[H <Home>')
call Allmap(' <ESC>[5~ <PageUp>')
call Allmap(' <ESC>[6~ <PageDown>')
call Allmap(' <ESC>[k4~ <C-Left>')
call Allmap(' <ESC>[5D <C-Left>')
call Allmap(' <ESC>Od <C-Left>')
call Allmap(' <ESC>[k6~ <C-Right>')
call Allmap(' <ESC>[5C <C-Right>')
call Allmap(' <ESC>Oc <C-Right>')
xterm's keybindings. You said this sometimes works and sometimes doesn't. You need to figure out what the difference in context is for when it works and when it doesn't. Does it matter what computer you are connecting from? What on earth do you mean by "your hosting provider provides you with an xterm", that is a strange statement. Do you have physical access to this machine? Are they X-forwarding you something? Do you mean they provide you a shell account you ssh into? What OS and Desktop Environment are you in? What is the server you are being provided with? – Caleb Aug 20 '11 at 13:11