I am not quite sure why the RadToolTip shows only for your first page - I assume that it could possibly be a missing rebinding of the GridView. If you don't rebind it, the row_databound event will not fire and the target controls would not be added to the RadToolTipManager's TargetControls collection.
I prepared a simple example which demonstrates the desired functionality - you can find it in the attached archive file. The GridView's ajaxifying is made by simply putting it in a RadAjaxPanel, you can also use a standard UpdatePanel control. I have enabled sorting in order to demonstrate that Ajax requests are thrown instead of postbacks.
I hope this would be helpful but in case you experience troubles, please, open a new support ticket and send us your project.
the Telerik team