pg_xlog not recycling WAL files on slave server
The problem seems to have been resolved. 

Apparently I had hardware issues on the master server.
I was able to perform full pg_dump and re-index my DB so I was pretty sure I did not have any data integrity issues.  

But when looking at the master server logs after I've enabled log_checkpoints in the config - a few minutes before the slave server stopped performing checkpoints I saw the following message:

IDT ERROR:  failed to re-find parent key in index "&lt;table_name&gt;_id_udx" for split pages 17/18


After seeing that - I decided to switch hosting provider and moved my DB to a new server.
Since then (almost a week now) - everything has been running smoothly replication and checkpoints are running as expected.

I really hope this will help other people - but when something like this is happening - always be advised that this issue might be caused by data integrity/hardware issues.