Not sure why the songs would stop appearing in Recently added playlist.

However, in the main music library you can add a Date Added column & arrange them that way via clicking the top of that column. Most recently added will be listed at top (make sure arrow is pointing down.) This will definitely work because if you are creating playlists, you will drag & drop them from the main music library. I always used this column before iTunes decided to add a Recently Added Playlist.

Sample image (click to see larger view)

* Note: if there are songs appearing in the Recently Added Playlist but they will not drag to other playlists, it means those particular songs have not been added to the main iTunes Library!!! How to transfer music to my iPod (& iTunes) {click on link}